Foundations and Trends® in Theoretical Computer Science > Vol 2 > Issue 1

Average-Case Complexity

By Andrej Bogdanov, DIMACS – Rutgers University, adib@dimacs.rutgers.edu | Luca Trevisan, UC Berkeley, luca@eecs.berkeley.edu

 
Suggested Citation
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

Publication Date: 19 Dec 2006
© 2006 A. Bogdanov and L. Trevisan
 
Subjects
Design and analysis of algorithms,  Randomness in computation
 

Free Preview:

Download extract

Share

Download article
In this article:
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 

Abstract

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.

DOI:10.1561/0400000004
ISBN: 978-1-933019-49-9
120 pp. $80.00
Buy book (pb)
 
ISBN: 978-1-933019-97-0
120 pp. $100.00
Buy E-book (.pdf)
Table of contents:
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

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.

 
TCS-004