EUVIMEDDescubrir EUVIMED
Crossref

Average-Case Complexity

Andrej Bogdanov, Luca Trevisan

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.

ResumenDatos bibliográficosCiteRelated studies

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}
}
Start for free →