Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
In the paper a new characterization of the strict \(\forall \Sigma^{b}_{j}\)-sentences provable using \(\Sigma^{b}_{k}\)-induction for \(1 \leq j \leq k\) is given. As an application it is shown that in a certain sense Buss's witnessing theorem for strict \(\Sigma^{b}_{k}\)-formulas already holds over the relatively weak theory PV. A combinatorial principle is exhibited with the property that a lower bound for it in constant-depth Frege would imply that the narrow CNFs with short depth-\(j\) Frege refutations form a strict hierarchy with \(j\), and hence that the relativized bounded arithmetic hierarchy can be separated by a family of \(\forall \Sigma^{b}_{1}\)-sentences.
- The provably total search problems of bounded arithmetic
- scientific article; zbMATH DE number 1344922
- Bounded arithmetic, proof complexity and two papers of Parikh
- scientific article; zbMATH DE number 1070621
- Characterising definable search problems in bounded arithmetic via proof notations
- Herbrandizing search problems in Bounded Arithmetic
- scientific article; zbMATH DE number 819737
- Total search problems in bounded arithmetic and improved witnessing
- scientific article; zbMATH DE number 806753
- scientific article; zbMATH DE number 1670480
- A form of feasible interpolation for constant depth Frege systems
- 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
- Bounded arithmetic and the polynomial hierarchy
- Characterising definable search problems in bounded arithmetic via proof notations
- Exponential lower bounds for the pigeonhole principle
- Fragments of bounded arithmetic and the lengths of proofs
- Herbrandizing search problems in Bounded Arithmetic
- scientific article; zbMATH DE number 4145897 (Why is no real title available?)
- scientific article; zbMATH DE number 3912375 (Why is no real title available?)
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 5038466 (Why is no real title available?)
- Lifting independence results in bounded arithmetic
- Notes on polynomially bounded arithmetic
- NP search problems in low fragments of bounded arithmetic
- On induction-free provability
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- Polynomial size proofs of the propositional pigeonhole principle
- Quantified propositional calculi and fragments of bounded arithmetic
- Relating the bounded arithmetic and polynomial time hierarchies
- The provably total search problems of bounded arithmetic
- What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?
- Witnessing functions in bounded arithmetic and search problems
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
- Witnessing functions in bounded arithmetic and search problems
- NP search problems in low fragments of bounded arithmetic
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Witnessing flows in arithmetic
This page was built for publication: Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q647334)
