Revision #1 Authors: Andrej Bogdanov, Luca Trevisan

Accepted on: 29th September 2006 00:00

Downloads: 2967

Keywords:

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''

results.

TR06-073 Authors: Andrej Bogdanov, Luca Trevisan

Publication: 8th June 2006 21:09

Downloads: 3110

Keywords:

We survey the theory of average-case complexity, with a

focus on problems in NP.