Canonical disjoint NP-pairs of propositional proof systems

DOI10.1016/J.TCS.2006.10.006MaRDI QIDQ868942zbMATHOpenAlexFDO

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

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

degreespropositional proof systemsdisjoint NP-pairsP-separable

Mathematics Subject Classification ID

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

Recommendations

• Mathematical Foundations of Computer Science 2005
• Theory and Applications of Models of Computation
• Disjoint NP-pairs and propositional proof systems
• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
• Classes of representable disjoint \textsf{NP}-pairs

Cites work

• scientific article; zbMATH DE number 3841832 (Why is no real title available?)
• scientific article; zbMATH DE number 3598538 (Why is no real title available?)
• scientific article; zbMATH DE number 1929970 (Why is no real title available?)
• scientific article; zbMATH DE number 1834681 (Why is no real title available?)
• A uniform approach to obtain diagonal sets in complexity classes
• Complexity Measures for Public-Key Cryptosystems
• Disjoint NP-Pairs
• Lattice embeddings for abstract bounded reducibilities
• On reducibility and symmetry of disjoint NP pairs.
• On the Structure of Polynomial Time Reducibility
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• The relative efficiency of propositional proof systems

Cited in

(17)

• Theory and Applications of Models of Computation
• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
• The deduction theorem for strong propositional proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• Mathematical Foundations of Computer Science 2005
• The Deduction Theorem for Strong Propositional Proof Systems
• A thirty year old conjecture about promise problems
• Unions of disjoint NP-complete sets
• Incompleteness in the finite domain
• Inseparability and strong hypotheses for disjoint NP pairs
• Dimension and the structure of complexity classes
• Do there exist complete sets for promise classes?
• The Informational Content of Canonical Disjoint NP-Pairs
• Nondeterministic functions and the existence of optimal proof systems
• Proof system representations of degrees of disjoint NP-pairs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q868942)