A Tight Karp-Lipton Collapse Result in Bounded Arithmetic

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

zbMATH Keywords

bounded arithmeticadviceKarp-Lipton theoremoptimal propositional proof systemsExtended Frege

Mathematics Subject Classification ID

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