THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS

DOI10.1142/S012905410900670XzbMath1178.68273MaRDI QIDQ3636159

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

Publication date: 30 June 2009

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

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)

Dimension and the structure of complexity classes ⋮ Proof system representations of degrees of disjoint NP-pairs

Cites Work

• Oracles for structural properties: The isomorphism problem and public-key cryptography
• Optimal proof systems imply complete sets for promise classes
• On reducibility and symmetry of disjoint NP pairs.
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Complexity Measures for Public-Key Cryptosystems
• Natural Self-Reducible Sets
• The relative efficiency of propositional proof systems

This page was built for publication: THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS