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/

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

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

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

Cites Work

scientific article; zbMATH DE number 3167429 (Why is no real title available?)
scientific article; zbMATH DE number 5485524 (Why is no real title available?)
scientific article; zbMATH DE number 3560738 (Why is no real title available?)
scientific article; zbMATH DE number 1306886 (Why is no real title available?)
scientific article; zbMATH DE number 1559537 (Why is no real title available?)
A comparison of polynomial time completeness notions
A comparison of polynomial time reducibilities
Bi-immunity separates strong NP-completeness notions
Comparing reductions to NP-complete sets
Complete Problems and Strong Polynomial Reducibilities
Completeness for nondeterministic complexity classes
Computational Complexity
Cook versus Karp-Levin: Separating completeness notions if NP is not small
Hardness vs randomness
Measure, Stochasticity, and the Density of Hard Languages
Non-uniform reductions
On Isomorphisms and Density of $NP$ and Other Complete Sets
On being incoherent without being very hard
On coherence, random-self-reducibility, and self-correction
On constructing 1-1 one-way functions
Partial bi-immunity, scaled dimension, and NP-completeness
Pseudorandom generators without the XOR lemma
Separating NP-completeness notions under strong hypotheses
Separation of NP-completeness notions
Some connections between bounded query classes and non-uniform complexity.
The complexity of theorem-proving procedures
The power of adaptiveness and additional queries in random-self- reductions
$BPP$ has subexponential time simulations unless $EXPTIME$ has publishable proofs
$p$-Selective sets and reducing search to decision vs. self-reducibility

Cited In (5)

Average-Case Completeness in Tag Systems
Collapsing and separating completeness notions under average-case and worst-case hypotheses
Separating Cook completeness from Karp-Levin completeness under a worst-case hardness hypothesis
NP-completeness notions under strong hypotheses
Properties of NP‐Complete Sets

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)