Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes

DOI10.1007/978-3-642-03351-3_7zbMath1248.03059OpenAlexW2143786941WikidataQ59903695 ScholiaQ59903695MaRDI QIDQ3392941

Zenon Sadowski, Olaf Beyersdorff

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

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items

NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Proof system representations of degrees of disjoint NP-pairs

Cites Work

• Nondeterministic functions and the existence of optimal proof systems
• Canonical disjoint NP-pairs of propositional proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• Complexity classes without machines: on complete languages for UP
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Optimal proof systems imply complete sets for promise classes
• On an optimal propositional proof system and the structure of easy subsets of TAUT.
• Reductions between disjoint NP-pairs
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Nondeterministic Instance Complexity and Proof Systems with Advice
• The relative efficiency of propositional proof systems
• Disjoint NP-Pairs
• Consequences of the provability of NP ⊆ P/poly
• Unnamed Item
• Unnamed Item