THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
From MaRDI portal
Publication:3636159
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)
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