Inseparability and strong hypotheses for disjoint NP pairs
From MaRDI portal
Publication:693061
DOI10.1007/s00224-011-9326-7zbMath1282.68113OpenAlexW2011854900WikidataQ60578957 ScholiaQ60578957MaRDI QIDQ693061
Jack H. Lutz, Elvira Mayordomo, Lance J. Fortnow
Publication date: 7 December 2012
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2010/2471/
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Canonical disjoint NP-pairs of propositional proof systems
- Diagonalizations over polynomial time computable sets
- Almost everywhere high nonuniform complexity
- Oracles for structural properties: The isomorphism problem and public-key cryptography
- Genericity and randomness over feasible probability measures
- Resource bounded randomness and weakly complete problems
- Separability and one-way functions
- Relative to a random oracle, NP is not small
- Reductions between disjoint NP-pairs
- The Informational Content of Canonical Disjoint NP-Pairs
- The complexity of promise problems with applications to public-key cryptography
- Complexity Measures for Public-Key Cryptosystems
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- The relative efficiency of propositional proof systems
- Equivalence of Measures of Complexity Classes
- Disjoint NP-Pairs
This page was built for publication: Inseparability and strong hypotheses for disjoint NP pairs
