On the Structure and Complexity of Symbolic Proofs of Polynomial Identities
Iddo Tzameret · 2008
A symbolic proof for establishing that a given arithmetic formula Φ computes the zero polynomial (or equivalently, that two given arithmetic formulas compute the same polynomial) is a sequence of formulas, starting with Φ and deriving the formula 0 by means of the standard polynomial-ring axioms applied to any subformula. Motivated by results in proof complexity and algebraic complexity, we investigate basic structural and complexity characterizations of symbolic proofs of polynomial identities. Specifically, we introduce fragments of symbolic proofs named analytic symbolic proofs, enjoying a natural property: a symbolic proof is analytic if one cannot introduce arbitrary new formulas throughout the proof (that is, formulas computing the zero polynomial which do not originate, in a precise manner, from the initial arithmetic formula). We establish exponential lower bounds on the lengths of analytic symbolic proofs operating with depth-3 arithmetic formulas, under a certain regularity condition on the structure of proofs (roughly, mimicking a tree-like structure). The hard instances are explicit and rely on small formulas for the symmetric polynomials.