Improved witnessing and local improvement principles for second-order bounded arithmetic

DOI10.1145/2559950zbMath1287.03105OpenAlexW2040502162MaRDI QIDQ5410329

Arnold Beckmann, Samuel R. Buss

Publication date: 16 April 2014

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2559950

zbMATH Keywords

bounded arithmeticpolynomial spaceprovably total functionslocal improvementNP search problemswitnessing

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Second- and higher-order arithmetic and fragments (03F35)

Related Items (12)

The NP Search Problems of Frege and Extended Frege Proofs ⋮ Approximate counting and NP search problems ⋮ Short proofs of the Kneser-Lovász coloring principle ⋮ Propositional Proofs in Frege and Extended Frege Systems (Abstract) ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ Unnamed Item ⋮ Bounded theories for polyspace computability ⋮ Truth definition for $\Delta _ 0$ formulas and PSPACE computations ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Towards a unified complexity theory of total functions ⋮ Quasipolynomial size proofs of the propositional pigeonhole principle

Cites Work

• Unnamed Item
• Unnamed Item
• The provably total NP search problems of weak second order bounded arithmetic
• Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
• Corrected upper bounds for free-cut elimination
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• Proof theory. 2nd ed
• What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?
• Relationships between nondeterministic and deterministic tape complexities
• The provably total search problems of bounded arithmetic
• POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
• Logical Foundations of Proof Complexity

This page was built for publication: Improved witnessing and local improvement principles for second-order bounded arithmetic