A Tight Karp-Lipton Collapse Result in Bounded Arithmetic

DOI10.1007/978-3-540-87531-4_16zbMATH Open1157.03032DBLPconf/csl/BeyersdorffM08OpenAlexW1503766551WikidataQ59903873 ScholiaQ59903873MaRDI QIDQ3540180FDOQ3540180

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

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

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)

Cites Work

• Title not available (Why is that?)
• Notes on polynomially bounded arithmetic
• Title not available (Why is that?)
• The relative efficiency of propositional proof systems
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• Bounded queries to SAT and the Boolean hierarchy
• Competing provers yield improved Karp-Lipton collapse results
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Title not available (Why is that?)
• Consequences of the provability of NP ⊆ P/poly
• Bounded arithmetic and the polynomial hierarchy
• Approximate counting in bounded arithmetic
• Title not available (Why is that?)
• New Collapse Consequences of NP Having Small Circuits
• Title not available (Why is that?)
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
• The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
• On an optimal propositional proof system and the structure of easy subsets of TAUT.

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)