Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
DOI10.1007/978-3-642-03351-3_7zbMATH Open1248.03059OpenAlexW2143786941WikidataQ59903695 ScholiaQ59903695MaRDI QIDQ3392941FDOQ3392941
Authors: Olaf Beyersdorff, Zenon Sadowski 
Publication date: 18 August 2009
Published in: Computer Science - Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03351-3_7
Recommendations
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)
Cites Work
- Complexity classes without machines: on complete languages for UP
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF
- Title not available (Why is that?)
- The relative efficiency of propositional proof systems
- Disjoint NP-Pairs
- Canonical disjoint NP-pairs of propositional proof systems
- Optimal proof systems imply complete sets for promise classes
- 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
- Reductions between disjoint NP-pairs
- Nondeterministic Instance Complexity and Proof Systems with Advice
- On an optimal propositional proof system and the structure of easy subsets of TAUT.
- Nondeterministic functions and the existence of optimal proof systems
- Classes of representable disjoint \textsf{NP}-pairs
Cited In (5)
This page was built for publication: Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3392941)
