A Tight Karp-Lipton Collapse Result in Bounded Arithmetic

DOI10.1007/978-3-540-87531-4_16MaRDI QIDQ3540180zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

advicebounded arithmeticKarp-Lipton theoremoptimal propositional proof systemsExtended Frege

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30)

Recommendations

• A tight Karp-Lipton collapse result in bounded arithmetic
• Consequences of the provability of NP ⊆ P/poly
• scientific article; zbMATH DE number 1962842
• Competing provers yield improved Karp-Lipton collapse results
• Nondeterministic Instance Complexity and Proof Systems with Advice

Cites work

• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3557241 (Why is no real title available?)
• scientific article; zbMATH DE number 1962843 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 2196512 (Why is no real title available?)
• Approximate counting in bounded arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Bounded queries to SAT and the Boolean hierarchy
• Competing provers yield improved Karp-Lipton collapse results
• Consequences of the provability of NP ⊆ P/poly
• New Collapse Consequences of NP Having Small Circuits
• Notes on polynomially bounded arithmetic
• 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 Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The relative efficiency of propositional proof systems
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)

Cited in

(4)

• Consequences of the provability of NP ⊆ P/poly
• A tight Karp-Lipton collapse result in bounded arithmetic
• Nondeterministic Instance Complexity and Proof Systems with Advice
• Does Advice Help to Prove Propositional Tautologies?

This page was built for publication: A Tight Karp-Lipton Collapse Result in Bounded Arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3540180)