Andrej Bogdanov and Luca Trevisan (2006), "Average-Case Complexity", Foundations and Trends® in Theoretical Computer Science: Vol. 2: No. 1, pp 1-106. http://dx.doi.org/10.1561/0400000004

© 2006 A. Bogdanov and L. Trevisan

1 Introduction

2 Definitions of "Efficient on Average"

3 A Complete Problem for Computable Ensembles

4 Decision Versus Search and One-Way Functions

5 Samplable Ensembles

6 Hardness Amplification

7 Worst-Case Versus Average-Case and Cryptography

8 Other Topics

A Samplable Ensembles Versus Samplable Distributions

Acknowledgments

References

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 some-what 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 is whether the existence of hard-on-average problems in NP can be based on the P ≠ 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.

1. Introduction

2. Definitions of "Efficient on Average"

3. A Complete Problem for Computable Ensembles

4. Decision versus Search and One-Way Functions

5. Samplable Ensembles

6. Hardness Amplification

7. Worst-Case versus Average-Case and Cryptography

8. Other Topics

Acknowledgements

References

Average-Case Complexity is a thorough survey of the average-case complexity of problems in NP. The study of the average-case complexity of intractable problems began in the 1970s, motivated by two distinct applications: the developments of the foundations of cryptography and the search for methods to "cope" with the intractability of NP-hard problems. This survey looks at both, and generally examines the current state of knowledge on average-case complexity. Average-Case Complexity is intended for scholars and graduate students in the field of theoretical computer science. The reader will also discover a number of results, insights, and proof techniques whose usefulness goes beyond the study of average-case complexity.