Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
From MaRDI portal
Publication:647334
DOI10.1007/s00153-011-0240-0zbMath1251.03077OpenAlexW1979972097MaRDI QIDQ647334
Publication date: 23 November 2011
Published in: Archive for Mathematical Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00153-011-0240-0
First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items
Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Improved witnessing and local improvement principles for second-order bounded arithmetic
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exponential lower bounds for the pigeonhole principle
- Bounded arithmetic and the polynomial hierarchy
- Lifting independence results in bounded arithmetic
- On induction-free provability
- Relating the bounded arithmetic and polynomial time hierarchies
- What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?
- The provably total search problems of bounded arithmetic
- Herbrandizing search problems in Bounded Arithmetic
- Quantified propositional calculi and fragments of bounded arithmetic
- A form of feasible interpolation for constant depth Frege systems
- POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
- Polynomial size proofs of the propositional pigeonhole principle
- Witnessing functions in bounded arithmetic and search problems
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- NP search problems in low fragments of bounded arithmetic
- Fragments of bounded arithmetic and the lengths of proofs
- Notes on polynomially bounded arithmetic
This page was built for publication: Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
