Canonical disjoint NP-pairs of propositional proof systems

DOI10.1016/j.tcs.2006.10.006zbMath1118.68070OpenAlexW1979054927MaRDI QIDQ868942

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

Publication date: 26 February 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.10.006

zbMATH Keywords

propositional proof systemsdegreesdisjoint NP-pairsP-separable

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (11)

Nondeterministic functions and the existence of optimal proof systems ⋮ A thirty year old conjecture about promise problems ⋮ Dimension and the structure of complexity classes ⋮ Proof system representations of degrees of disjoint NP-pairs ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Inseparability and strong hypotheses for disjoint NP pairs ⋮ The deduction theorem for strong propositional proof systems ⋮ The Deduction Theorem for Strong Propositional Proof Systems ⋮ Unions of Disjoint NP-Complete Sets ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ Do there exist complete sets for promise classes?

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A uniform approach to obtain diagonal sets in complexity classes
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• On reducibility and symmetry of disjoint NP pairs.
• Lattice Embeddings for Abstract Bounded Reducibilities
• Complexity Measures for Public-Key Cryptosystems
• On the Structure of Polynomial Time Reducibility
• The relative efficiency of propositional proof systems
• Disjoint NP-Pairs

This page was built for publication: Canonical disjoint NP-pairs of propositional proof systems