Average-Case Complexity
Foundations and Trends® in Theoretical Computer Science · 2006
DOI: 10.1561/0400000004 ↗At a glance
Journal article in Foundations and Trends® in Theoretical Computer Science, 2006. Written by Andrej Bogdanov and 1 co-authors. Cited 78 times so far (Crossref); 76 references.
Abstract (original language)
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.
Cite
APA
Bogdanov, A., & Trevisan, L. (2006). Average-Case Complexity. Foundations and Trends® in Theoretical Computer Science. https://doi.org/10.1561/0400000004
Vancouver
Bogdanov A, Trevisan L. Average-Case Complexity. Foundations and Trends® in Theoretical Computer Science. 2006. doi:10.1561/0400000004
BibTeX
@article{Bogdanov2006,
author = {Bogdanov, Andrej and Trevisan, Luca},
title = {Average-Case Complexity},
journal = {Foundations and Trends® in Theoretical Computer Science},
year = {2006},
doi = {10.1561/0400000004}
}
EUVIMED