Proof systems that take advice

DOI10.1016/J.IC.2010.11.006zbMath1222.03062DBLPjournals/iandc/BeyersdorffKM11OpenAlexW2059785423WikidataQ59902997 ScholiaQ59902997MaRDI QIDQ553297

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

Publication date: 27 July 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2010.11.006

zbMATH Keywords

computational complexityadviceproof systemspropositional proof complexityinstance complexityoptimal proof systemspolynomially bounded proof systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20)

Related Items (3)

Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ On the amount of nonconstructivity in learning formal languages from text ⋮ Do there exist complete sets for promise classes?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logarithmic advice classes
• Optimal proof systems imply complete sets for promise classes
• Competing provers yield improved Karp-Lipton collapse results
• Resource-Bounded Kolmogorov Complexity Revisited
• A tight Karp-Lipton collapse result in bounded arithmetic
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Nondeterministic Instance Complexity and Proof Systems with Advice
• Does Advice Help to Prove Propositional Tautologies?
• The relative efficiency of propositional proof systems
• Instance complexity
• Tally languages and complexity classes
• Consequences of the provability of NP ⊆ P/poly

This page was built for publication: Proof systems that take advice