The Informational Content of Canonical Disjoint NP-Pairs

DOI10.1007/978-3-540-73545-8_31zbMath1178.68275OpenAlexW2122215055MaRDI QIDQ3608856

Liyu Zhang, Selman, Alan L., 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

zbMATH Keywords

propositional proof systemscanonical pairsP-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)

Related Items (2)

Nondeterministic functions and the existence of optimal proof systems ⋮ Inseparability and strong hypotheses for disjoint NP pairs

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