Circuit Complexity, Proof Complexity, and Polynomial Identity Testing

We introduce a new and natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits (VNP≠VP). As a corollary, super-polynomial lower bounds on the number of lines in Polynomial Calculus proofs (as opposed to the usual measure of number of monomials) imply the Permanent versus Determinant Conjecture. Note that, prior to our work, there was no proof system for which lower bounds on an arbitrary tautology implied any computational lower bound. Our proof system helps clarify the relationships between previous algebraic proof systems, and begins to shed light on why proof complexity lower bounds for various proof systems have been so much harder than lower bounds on the corresponding circuit classes. In doing so, we highlight the importance of polynomial identity testing (PIT) for understanding proof complexity.

Authors

• Joshua A. Grochow
• Toniann Pitassi

Keywords

• Complexity theory
• Polynomials
• Calculus
• Standards
• Testing
• Frequency modulation
• Complex Circuits
• Proof Complexity
• Polynomial Identity Testing
• Lower Bound
• Monomial
• Algebraic System
• New Variables
• General Questions
• Complexity Measures
• Polynomial Of Degree
• Finite Field
• Set Of Polynomials
• Circuit Size
• Algebraic Closure
• Polynomials In Variables
• AC0[p]-Frege
• algebraic circuit complexity
• Grobner bases
• lower bounds
• syzygies