Mathematical Foundations of Computer Science 2005

DOI10.1007/11549345MaRDI QIDQ5492875zbMATH OpenOpenAlexFDO

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

Publication date 20 October 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11549345

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Canonical disjoint NP-pairs of propositional proof systems
• Disjoint NP-pairs and propositional proof systems
• Theory and Applications of Models of Computation
• NP-Completeness, Proof Systems, and Disjoint NP-Pairs.
• Proof system representations of degrees of disjoint NP-pairs
• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
• The Informational Content of Canonical Disjoint NP-Pairs
• scientific article; zbMATH DE number 1765698
• P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
• Inseparability and strong hypotheses for disjoint NP pairs

Cited in

(17)

• On reducibility and symmetry of disjoint NP pairs.
• Proof system representations of degrees of disjoint NP-pairs
• The canonical pairs of bounded depth Frege systems
• Inseparability and strong hypotheses for disjoint NP pairs
• Tuples of Disjoint NP-Sets
• Disjoint NP-pairs and propositional proof systems
• The Informational Content of Canonical Disjoint NP-Pairs
• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
• scientific article; zbMATH DE number 1834681 (Why is no real title available?)
• P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
• A limitation on the KPT interpolation
• The Deduction Theorem for Strong Propositional Proof Systems
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Theory and Applications of Models of Computation
• Canonical disjoint NP-pairs of propositional proof systems
• Classes of representable disjoint \textsf{NP}-pairs
• The deduction theorem for strong propositional proof systems

This page was built for publication: Mathematical Foundations of Computer Science 2005

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