Algebraic proofs over noncommutative formulas

作者：Tzameret, Iddo^*

来源：Information and Computation, 2011, 209(10): 1269-1292.

DOI：10.1016/j.ic.2011.07.004

• Proof complexity
• Algebraic proof systems
• Frege proofs
• Lower bounds
• Noncommutative formulas
• Polynomial calculus

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege, yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analog of Frege proofs, different from that given in Buss et al. (1997) and Grigoriev and Hirsch (2003). We then turn to an apparently weaker system, namely, polynomial calculus (PC) where polynomials are written as ordered formulas (PC over ordered formulas, for short). Given some fixed linear order on variables, an arithmetic formula is ordered if for each of its product gates the left subformula contains only variables that are less-than or equal, according to the linear order, than the variables in the right subformula of the gate. We show that PC over ordered formulas (when the base field is of zero characteristic) is strictly stronger than resolution, polynomial calculus and polynomial calculus with resolution (PCR), and admits polynomial-size refutations for the pigeonhole principle and Tseitin's formulas. We conclude by proposing an approach for establishing lower bounds on PC over ordered formulas proofs, and related systems, based on properties of lower bounds on noncommutative formulas (Nisan, 1991).
The motivation behind this work is developing techniques incorporating rank arguments (similar to those used in arithmetic circuit complexity) for establishing lower bounds on propositional proofs.

• 出版日期2011-10
• 单位清华大学