Optimal proof systems imply complete sets for promise classes

DOI10.1016/S0890-5401(03)00058-0zbMath1029.03048OpenAlexW2080818057MaRDI QIDQ1398371

Johannes Köbler, Jochen Messner, Jacobo Toran

Publication date: 29 July 2003

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

Full work available at URL: https://doi.org/10.1016/s0890-5401(03)00058-0

zbMATH Keywords

Complete setsOptimal proof systems

Mathematics Subject Classification ID

Complexity of proofs (03F20)

Related Items (24)

Nondeterministic functions and the existence of optimal proof systems ⋮ A Parameterized Halting Problem ⋮ Reductions between disjoint NP-pairs ⋮ Classes of representable disjoint \textsf{NP}-pairs ⋮ Logical Closure Properties of Propositional Proof Systems ⋮ Towards NP-P via proof complexity and search ⋮ The Shrinking Property for NP and coNP ⋮ The shrinking property for NP and coNP ⋮ Further oracles separating conjectures about incompleteness in the finite domain ⋮ Tuples of disjoint \(\mathsf{NP}\)-sets ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Total nondeterministic Turing machines and a p-optimal proof system for SAT ⋮ Proof systems that take advice ⋮ The deduction theorem for strong propositional proof systems ⋮ The Complexity of Propositional Proofs ⋮ An oracle separating conjectures about incompleteness in the finite domain ⋮ Hard Instances of Algorithms and Proof Systems ⋮ The Deduction Theorem for Strong Propositional Proof Systems ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS ⋮ Does Advice Help to Prove Propositional Tautologies? ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle ⋮ Do there exist complete sets for promise classes?

Cites Work

• Complexity classes without machines: on complete languages for UP
• A uniform approach to define complexity classes
• Universal classes of hash functions
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• On Approximation Algorithms for # P
• The relative efficiency of propositional proof systems
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Tally languages and complexity classes
• The Complexity of Propositional Proofs
• On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP
• On the power of parity polynomial time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Optimal proof systems imply complete sets for promise classes