Does Advice Help to Prove Propositional Tautologies?
From MaRDI portal
Publication:3637158
DOI10.1007/978-3-642-02777-2_8zbMath1247.03119OpenAlexW1533547276WikidataQ59903690 ScholiaQ59903690MaRDI QIDQ3637158
Olaf Beyersdorff, Sebastian Müller
Publication date: 7 July 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: http://eprints.whiterose.ac.uk/74803/2/SAT09-advice.pdf
Related Items
Cites Work
- Logarithmic advice classes
- Optimal proof systems imply complete sets for promise classes
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- A Tight Karp-Lipton Collapse Result in Bounded Arithmetic
- Nondeterministic Instance Complexity and Proof Systems with Advice
- The relative efficiency of propositional proof systems
- Consequences of the provability of NP ⊆ P/poly