EUVIMEDEUVIMED entdecken
Crossref

Average-Case Complexity

Andrej Bogdanov, Luca Trevisan

Foundations and Trends® in Theoretical Computer Science · 2006

DOI: 10.1561/0400000004 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Foundations and Trends® in Theoretical Computer Science, 2006. Verfasst von Andrej Bogdanov und 1 weiteren Autor:innen. Die Arbeit wurde bisher 78-mal zitiert (Crossref) und nennt 76 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

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}
}
Kostenlos starten →