Collapsing and separating completeness notions under average-case and worst-case hypotheses
DOI10.1007/S00224-011-9365-0zbMATH Open1253.68150OpenAlexW1568724636MaRDI QIDQ693053FDOQ693053
Authors: Xiaoyang Gu, John M. Hitchcock, Aduri Pavan 
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/
Recommendations
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- scientific article; zbMATH DE number 4074483
- Separating Cook completeness from Karp-Levin completeness under a worst-case hardness hypothesis
- Reductions, completeness and the hardness of approximability
- scientific article; zbMATH DE number 3883611
- scientific article; zbMATH DE number 1222584
- Average-case intractability vs. worst-case intractability
- On the Average Case Complexity of Some P-complete Problems
- Complete on average Boolean satisfiability
- Worst-case expansions of complete theories
computational complexityNP-completenessTuring completenessapproximable setslength-increasing reductions
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Computational Complexity
- Hardness vs randomness
- The complexity of theorem-proving procedures
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Measure, Stochasticity, and the Density of Hard Languages
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Title not available (Why is that?)
- Pseudorandom generators without the XOR lemma
- Completeness for nondeterministic complexity classes
- Title not available (Why is that?)
- Bi-immunity separates strong NP-completeness notions
- Separation of NP-completeness notions
- Separating NP-completeness notions under strong hypotheses
- A comparison of polynomial time reducibilities
- Title not available (Why is that?)
- A comparison of polynomial time completeness notions
- Title not available (Why is that?)
- On constructing 1-1 one-way functions
- Complete Problems and Strong Polynomial Reducibilities
- \(p\)-Selective sets and reducing search to decision vs. self-reducibility
- Title not available (Why is that?)
- On being incoherent without being very hard
- On coherence, random-self-reducibility, and self-correction
- The power of adaptiveness and additional queries in random-self- reductions
- Some connections between bounded query classes and non-uniform complexity.
- Non-uniform reductions
- Partial bi-immunity, scaled dimension, and NP-completeness
- Comparing reductions to NP-complete sets
Cited In (4)
This page was built for publication: Collapsing and separating completeness notions under average-case and worst-case hypotheses
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q693053)
