Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR06-073 | 29th September 2006 00:00

Average-Case Complexity


Revision #1
Authors: Andrej Bogdanov, Luca Trevisan
Accepted on: 29th September 2006 00:00
Downloads: 1293


We survey the average-case complexity of problems in NP.

We discuss various notions of good-on-average algorithms, and
present completeness results due to Impagliazzo and Levin.
Such completeness results establish the fact that if a certain
specific (but somewhat artificial) NP problem is easy-on-average
with respect to the uniform distribution, then all problems in NP
are easy-on-average with respect to all samplable distributions.
Applying the theory to natural distributional problems remain an
outstanding open question. We review some natural distributional
problems whose average-case complexity is of particular interest and
that do not yet fit into this theory.

A major open question whether the existence of hard-on-average
problems in NP can be based on the P$\neq$NP assumption or on
related worst-case assumptions. We review negative results showing
that certain proof techniques cannot prove such a result. While the
relation between worst-case and average-case complexity for general
NP problems remains open, there has been progress in understanding
the relation between different ``degrees'' of average-case
complexity. We discuss some of these ``hardness amplification''


TR06-073 | 8th June 2006 00:00

Average-Case Complexity

Authors: Andrej Bogdanov, Luca Trevisan
Publication: 8th June 2006 21:09
Downloads: 1400


We survey the theory of average-case complexity, with a
focus on problems in NP.

ISSN 1433-8092 | Imprint