Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem
From MaRDI portal
Publication:647334
DOI10.1007/S00153-011-0240-0zbMATH Open1251.03077OpenAlexW1979972097MaRDI QIDQ647334FDOQ647334
Authors: Neil Thapen 
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
Recommendations
- 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
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Notes on polynomially bounded arithmetic
- Title not available (Why is that?)
- The provably total search problems of bounded arithmetic
- Title not available (Why is that?)
- Polynomial size proofs of the propositional pigeonhole principle
- Title not available (Why is that?)
- An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
- Exponential lower bounds for the pigeonhole principle
- Herbrandizing search problems in Bounded Arithmetic
- An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
- Bounded arithmetic and the polynomial hierarchy
- Quantified propositional calculi and fragments of bounded arithmetic
- Characterising definable search problems in bounded arithmetic via proof notations
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- NP search problems in low fragments of bounded arithmetic
- Fragments of bounded arithmetic and the lengths of proofs
- On induction-free provability
- Relating the bounded arithmetic and polynomial time hierarchies
- Title not available (Why is that?)
- Lifting independence results in bounded arithmetic
- What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?
- A form of feasible interpolation for constant depth Frege systems
- Witnessing functions in bounded arithmetic and search problems
Cited In (6)
- NP search problems in low fragments of bounded arithmetic
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic
- Witnessing functions in bounded arithmetic and search problems
- Witnessing flows in arithmetic
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs
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)
