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

DOI10.1007/s00224-011-9365-0zbMath1253.68150OpenAlexW1568724636MaRDI 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 complexityNP-completenessTuring completenessapproximable setslength-increasing reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

This page was built for publication: Collapsing and separating completeness notions under average-case and worst-case hypotheses