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
bounded arithmeticpolynomial spaceprovably total functionslocal improvementNP search problemswitnessing
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)
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