A second-order system for polytime reasoning based on Grädel's theorem

✍ Scribed by Stephen Cook; Antonina Kolokolova

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 461 KB
• Volume: 124
• Category: Article
• ISSN: 0168-0072
• DOI: 10.1016/s0168-0072(03)00056-3

✦ Synopsis

We introduce a second-order system V1-Horn of bounded arithmetic formalizing polynomialtime reasoning, based on Gr adel's (Theoret. Comput. Sci. 101 (1992) 35) second-order Horn characterization of P. Our system has comprehension over P predicates (deÿned by Gr adel's second-order Horn formulas), and only ÿnitely many function symbols. Other systems of polynomial-time reasoning either allow induction on NP predicates (such as Buss's S 1 2 or the second-order V 1 1 ), and hence are more powerful than our system (assuming the polynomial hierarchy does not collapse), or use Cobham's theorem to introduce function symbols for all polynomial-time functions (such as Cook's PV and Zambella's P-def). We prove that our system is equivalent to QPV and Zambella's P-def. Using our techniques, we also show that V1-Horn is ÿnitely axiomatizable, and, as a corollary, that the class of ∀ b 1 consequences of S 1 2 is ÿnitely axiomatizable as well, thus answering an open question.