Nondeterministic Instance Complexity and Proof Systems with Advice

DOI10.1007/978-3-642-00982-2_14zbMath1234.03035OpenAlexW1567771348WikidataQ59903686 ScholiaQ59903686MaRDI QIDQ3618578

Sebastian Müller, Olaf Beyersdorff, Johannes Köbler

Publication date: 2 April 2009

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: http://eprints.whiterose.ac.uk/74796/2/nic_rev.pdf

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items

Proof systems that take advice ⋮ Does Advice Help to Prove Propositional Tautologies? ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Competing provers yield improved Karp-Lipton collapse results
• Resource-Bounded Kolmogorov Complexity Revisited
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
• The relative efficiency of propositional proof systems
• Instance complexity
• Consequences of the provability of NP ⊆ P/poly