A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
From MaRDI portal
Publication:3540180
DOI10.1007/978-3-540-87531-4_16zbMath1157.03032OpenAlexW1503766551WikidataQ59903873 ScholiaQ59903873MaRDI QIDQ3540180
Olaf Beyersdorff, Sebastian Müller
Publication date: 20 November 2008
Published in: Computer Science Logic (Search for Journal in Brave)
Full work available at URL: http://eprints.whiterose.ac.uk/74793/2/advicefinal.pdf
First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)
Related Items (2)
Nondeterministic Instance Complexity and Proof Systems with Advice ⋮ Does Advice Help to Prove Propositional Tautologies?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- Bounded arithmetic and the polynomial hierarchy
- Bounded queries to SAT and the Boolean hierarchy
- Competing provers yield improved Karp-Lipton collapse results
- On an optimal propositional proof system and the structure of easy subsets of TAUT.
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
- The relative efficiency of propositional proof systems
- New Collapse Consequences of NP Having Small Circuits
- The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
- Approximate counting in bounded arithmetic
- Consequences of the provability of NP ⊆ P/poly
- Notes on polynomially bounded arithmetic
This page was built for publication: A Tight Karp-Lipton Collapse Result in Bounded Arithmetic