Collapsing and separating completeness notions under average-case and worst-case hypotheses
From MaRDI portal
Publication:693053
DOI10.1007/s00224-011-9365-0zbMath1253.68150MaRDI QIDQ693053
A. Pavan, Xiaoyang Gu, John M. Hitchcock
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/2462/
computational complexity; NP-completeness; Turing completeness; approximable sets; length-increasing reductions
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Comparing reductions to NP-complete sets
- A comparison of polynomial time completeness notions
- On being incoherent without being very hard
- A comparison of polynomial time reducibilities
- On coherence, random-self-reducibility, and self-correction
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- The power of adaptiveness and additional queries in random-self- reductions
- Hardness vs randomness
- Some connections between bounded query classes and non-uniform complexity.
- \(p\)-Selective sets and reducing search to decision vs. self-reducibility
- Bi-immunity separates strong NP-completeness notions
- Non-uniform reductions
- Partial bi-immunity, scaled dimension, and NP-completeness
- Separation of NP-Completeness Notions
- On Constructing 1-1 One-Way Functions
- Completeness for nondeterministic complexity classes
- Complete Problems and Strong Polynomial Reducibilities
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Measure, Stochasticity, and the Density of Hard Languages
- Computational Complexity
- The complexity of theorem-proving procedures
- Separating NP-completeness notions under strong hypotheses
- Pseudorandom generators without the XOR lemma
