Canonical disjoint NP-pairs of propositional proof systems

DOI10.1016/J.TCS.2006.10.006zbMATH Open1118.68070OpenAlexW1979054927MaRDI QIDQ868942FDOQ868942

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

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

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

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)

Cites Work

• On the Structure of Polynomial Time Reducibility
• The relative efficiency of propositional proof systems
• Complexity Measures for Public-Key Cryptosystems
• Disjoint NP-Pairs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• On reducibility and symmetry of disjoint NP pairs.
• A uniform approach to obtain diagonal sets in complexity classes
• Lattice embeddings for abstract bounded reducibilities
• Title not available (Why is that?)

Cited In (17)

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

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)