Non-uniform reductions
From MaRDI portal
Publication:1959376
DOI10.1007/s00224-008-9163-5zbMath1206.68129OpenAlexW2137788273MaRDI QIDQ1959376
Leen Torenvliet, Harry Buhrman, Benjamin J. Hescott, Homer, Steven
Publication date: 6 October 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-008-9163-5
non-uniform complexityNP-complete setEXP-complete setNEXP-complete setnon-uniform reductionsreductions with advice
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Unnamed Item ⋮ Nonuniform reductions and NP-completeness ⋮ Autoreducibility of NP-complete sets under strong hypotheses ⋮ Collapsing and separating completeness notions under average-case and worst-case hypotheses
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A comparison of polynomial time completeness notions
- The complexity of optimization problems
- Isomorphisms and 1-L reductions
- Oracles for structural properties: The isomorphism problem and public-key cryptography
- A comparison of polynomial time reducibilities
- On 1-truth-table-hard languages
- The relative power of logspace and polynomial time reductions
- Almost every set in exponential time is P-bi-immune
- An excursion to the Kolmogorov random strings
- One-way functions and the nonisomorphism of NP-complete sets
- Comparing Reductions to NP-Complete Sets
- Completeness for nondeterministic complexity classes
- Complete Problems and Strong Polynomial Reducibilities
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- The isomorphism conjecture fails relative to a random oracle
- Separating Complexity Classes Using Autoreducibility
- Non-mitotic Sets
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Power from Random Strings
- Computability and complexity theory
