ECCC-Report TR06-073https://eccc.weizmann.ac.il/report/2006/073Comments and Revisions published for TR06-073en-usFri, 29 Sep 2006 00:00:00 +0300
Revision 1
| Average-Case Complexity |
Andrej Bogdanov,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2006/073#revision1We 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''
results.
Fri, 29 Sep 2006 00:00:00 +0300https://eccc.weizmann.ac.il/report/2006/073#revision1
Paper TR06-073
| Average-Case Complexity |
Andrej Bogdanov,
Luca Trevisan
https://eccc.weizmann.ac.il/report/2006/073We survey the theory of average-case complexity, with a
focus on problems in NP.
Thu, 08 Jun 2006 21:09:57 +0300https://eccc.weizmann.ac.il/report/2006/073