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

Average-Case Complexity

  • Andrej Bogdanov 1
  • Luca Trevisan 2

[1]Andrej Bogdanov, DIMACS – Rutgers University, [2]Luca Trevisan, UC Berkeley,

Short description

Average-Case Complexity is a thorough survey of the average-case complexity of problems in NP.


Subscribers Download

(non-subscribers see Book Details tab if available)

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
A Samplable Ensembles Versus Samplable Distributions

Foundations and Trends® in Theoretical Computer Science

(Vol 2, Issue 1, 2006, pp 1-106)

DOI: 10.1561/0400000004


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.

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
Cover image for Average-Case Complexity

Average-Case Complexity

120 pages

DOI: 10.1561/9781933019970

E-ISBN: 978-1-933019-97-0

ISBN: 978-1-933019-49-9


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.