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

DOI10.1007/978-3-642-03351-3_7MaRDI QIDQ3392941zbMATH OpenOpenAlexWikidataFDO

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

Mathematics Subject Classification ID

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

Recommendations

• Do there exist complete sets for promise classes?
• Optimal proof systems imply complete sets for promise classes
• scientific article; zbMATH DE number 1500532
• scientific article; zbMATH DE number 1335888
• scientific article; zbMATH DE number 1136087

Cites work

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

Cited in

(5)

• Proof systems that take advice
• Optimal proof systems imply complete sets for promise classes
• Proof system representations of degrees of disjoint NP-pairs
• Do there exist complete sets for promise classes?
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN

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)