Collapsing and separating completeness notions under average-case and worst-case hypotheses

DOI10.1007/s00224-011-9365-0zbMath1253.68150MaRDI QIDQ693053

John M. Hitchcock, A. Pavan, Xiaoyang Gu

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/

zbMATH Keywords

computational complexity; NP-completeness; Turing completeness; approximable sets; length-increasing reductions

Mathematics Subject Classification ID

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