Vi introducerar ett nytt och naturligt algebraiskt bevissystem, som har täta kopplingar till (algebraisk) krets komplexitet. I synnerhet visar vi att varje super-polynom lägre bundet på någon Boolesk tautologi i vårt bevissystem innebär att den permanenta inte har polynom-storlek algebraiska kretsar (VNP = VP). Som en korollär, super-polynom lägre gränser på antalet linjer i Polynomial Calculus bevis (i motsats till det vanliga måttet på antalet monomials) innebär Permanent kontra Determinant Conjecture. Observera att det före vårt arbete inte fanns något bevissystem för vilket lägre gränser på en godtycklig tautologi innebar någon beräkningsmässig lägre gräns. Vårt bevissystem hjälper till att klargöra förhållandet mellan tidigare algebraiska bevissystem, och börjar belysa varför bevis komplexitet lägre gränser för olika bevissystem har varit så mycket svårare än lägre gränser på motsvarande kretsklasser. I detta sammanhang betonar vi vikten av polynomisk identitetsprövning (PIT) för att förstå bevisets komplexitet.
Grochow och Pitassi REF, med avseende på vårt arbete för att bevisa komplexitet, införde ett nytt algebraiskt bevissystem baserat på axiom som är nöjda med alla booleska kretsar som löser problemet med polynomiska identitetstester.
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing
{'venue': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'journal': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science', 'Mathematics']}