Disjoint NP-Pairs

DOI10.1137/S0097539703425848zbMath1101.68595OpenAlexW2081065305MaRDI QIDQ4651518

Samik Sengupta, Liyu Zhang, Christian Glaßer, Selman, Alan L.

Publication date: 21 February 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539703425848

zbMATH Keywords

symmetrypropositional proof systemspromise problemsoraclesdisjoint NP-pairs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (21)

Nondeterministic functions and the existence of optimal proof systems ⋮ Reductions between disjoint NP-pairs ⋮ A thirty year old conjecture about promise problems ⋮ Canonical disjoint NP-pairs of propositional proof systems ⋮ Classes of representable disjoint \textsf{NP}-pairs ⋮ NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Dimension and the structure of complexity classes ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ The Shrinking Property for NP and coNP ⋮ The shrinking property for NP and coNP ⋮ Proof system representations of degrees of disjoint NP-pairs ⋮ Further oracles separating conjectures about incompleteness in the finite domain ⋮ Tuples of disjoint \(\mathsf{NP}\)-sets ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Inseparability and strong hypotheses for disjoint NP pairs ⋮ The deduction theorem for strong propositional proof systems ⋮ An oracle separating conjectures about incompleteness in the finite domain ⋮ The Deduction Theorem for Strong Propositional Proof Systems ⋮ 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?

This page was built for publication: Disjoint NP-Pairs