Relating the Provable Collapse of P to NC¹ and the Power of Logical Theories
Stephen A Cook · 2007
We show that the following three statements are equivalent: QPV is conservative over QALV, QALV proves its open induction formulas, and QALV proves P=NC¹. Here QPV and QALV are first order theories whose function symbols range over polynomial-time and NC¹ functions, respectively.