The Informational Content of Canonical Disjoint NP-Pairs

DOI10.1007/978-3-540-73545-8_31zbMATH Open1178.68275OpenAlexW2122215055MaRDI QIDQ3608856FDOQ3608856

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

Publication date: 6 March 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-540-73545-8_31

Recommendations

• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
• Mathematical Foundations of Computer Science 2005
• Theory and Applications of Models of Computation
• Canonical disjoint NP-pairs of propositional proof systems
• Disjoint NP-pairs and propositional proof systems

zbMATH Keywords

canonical pairspropositional proof systemsP-inseparable NP-pairsunions of disjoint NP-complete sets

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Cited In (4)

• Inseparability and strong hypotheses for disjoint NP pairs
• Nondeterministic functions and the existence of optimal proof systems
• Mathematical Foundations of Computer Science 2005
• THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS

This page was built for publication: The Informational Content of Canonical Disjoint NP-Pairs

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