Average-case complexity: Difference between revisions

Revision as of 19:19, 15 November 2024

Revision as of 20:38, 21 May 2025

Line 2:

In [[computational complexity theory]], the '''average-case complexity''' of an [[algorithm]] is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with [[worst-case complexity]] which considers the maximal complexity of the algorithm over all possible inputs.

There are three primary motivations for studying average-case complexity.<ref name="gol07">O.{{Cite journal |last=Goldreich and S.|first=Oded |last2=Vadhan, |first2=Salil |date=2007-12 |title=Special issueIssue onOn worstWorst-case versusVersus averageAverage-case complexity,Complexity Comput.Editors’ ComplexForeword |url=https://link.springer.com/10.1007/s00037-007-0232-y |journal=computational complexity |language=en |volume=16, |issue=4 |pages=325–330, 2007|doi=10.1007/s00037-007-0232-y |issn=1016-3328}}</ref> First, although some problems may be intractable in the worst-case, the inputs which elicit this behavior may rarely occur in practice, so the average-case complexity may be a more accurate measure of an algorithm's performance. Second, average-case complexity analysis provides tools and techniques to generate hard instances of problems which can be utilized in areas such as [[cryptography]] and [[derandomization]]. Third, average-case complexity allows discriminating the most efficient algorithm in practice among algorithms of equivalent best case complexity (for instance [[Quicksort#Formal analysis|Quicksort]]).

Average-case analysis requires a notion of an "average" input to an algorithm, which leads to the problem of devising a [[probability distribution]] over inputs. Alternatively, a [[randomized algorithm]] can be used. The analysis of such algorithms leads to the related notion of an '''expected complexity'''.<ref name="clrs"/>{{rp|28}}

Line 66:

In his original paper, Levin showed an example of a distributional tiling problem that is average-case {{math|'''NP'''}}-complete.<ref name="levin86"/> A survey of known {{math|'''distNP'''}}-complete problems is available online.<ref name="wangsurvey"/>

One area of active research involves finding new {{math|'''distNP'''}}-complete problems. However, finding such problems can be complicated due to a result of Gurevich which shows that any distributional problem with a flat distribution cannot be {{math|'''distNP'''}}-complete unless [[EXP|{{math|'''EXP'''}}]] = [[NEXP|{{math|'''NEXP'''}}]].<ref name="gur87">Y. Gurevich, "Complete and incomplete randomized NP problems", Proc. 28th Annual Symp. on Found. of Computer Science, IEEE (1987), pp. 111–117.</ref> (A flat distribution {{mvar|μ}} is one for which there exists an {{math|''ε'' &gt; 0}} such that for any {{mvar|x}}, {{math|''μ''(''x'') ≤ 2^{−{{abs|''x''}}^''ε''}}}.) A result by Livne shows that all natural {{math|'''NP'''}}-complete problems have {{math|'''DistNP'''}}-complete versions.<ref name="livne06">N. Livne, "All Natural NP-Complete Problems Have Average-Case Complete Versions," Computational Complexity (2010) 19:477. https://doi.org/10.1007/s00037-010-0298-9</ref> However, the goal of finding a natural distributional problem that is {{math|'''DistNP'''}}-complete has not yet been achieved.<ref name="gol97">O.{{Citation |last=Goldreich, "|first=Oded |title=Notes on Levin'sLevin’s theoryTheory of averageAverage-caseCase complexity,"Complexity Technical|date=2011 Report|work=Studies TR97-058,in ElectronicComplexity Colloquiumand Cryptography. Miscellanea on Computationalthe ComplexityInterplay between Randomness and Computation |volume=6650 |pages=233–247 |editor-last=Goldreich |editor-first=Oded |url=http://link.springer.com/10.1007/978-3-642-22670-0_21 |access-date=2025-05-21 |place=Berlin, 1997Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/978-3-642-22670-0_21 |isbn=978-3-642-22669-4}}</ref>

==Applications==

Line 104:

==Further reading==

Pedagogical presentations:

* {{cite book |last1=Arora |first1=Sanjeev |title=Computational Complexity: A Modern Approach |last2=Barak |first2=Boaz |date=2009 |publisher=Cambridge University Press |___location=Cambridge ; New York |chapter=18. Average case complexity: Levin’s theory}}

* {{cite book |last1=Wang |first1=Jie |url=https://www.cs.uml.edu/~wang/acc-forum/avgcomp.pdf |title=Complexity Theory: Retrospective II |date=1997 |publisher=Springer Science & Business Media |editor-last1=Hemaspaandra |editor-first1=Lane A. |volume=2 |pages=295–328 |chapter=Average-case computational complexity theory |editor-last2=Selman |editor-first2=Alan L.}}

* {{Citation |last=Goldreich |first=Oded |title=Average Case Complexity, Revisited |date=2011 |work=Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation |volume=6650 |pages=422–450 |editor-last=Goldreich |editor-first=Oded |url=https://www.wisdom.weizmann.ac.il/~oded/COL/aver.pdf |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/978-3-642-22670-0_29 |isbn=978-3-642-22669-4}}

The literature of average case complexity includes the following work:

*{{citation

| last = Franco | first = John

| doi = 10.1016/0020-0190(86)90051-7

| issue = 2

| journal = Information Processing Letters

| pages = 103–106

| title = On the probabilistic performance of algorithms for the satisfiability problem

| volume = 23

| year = 1986}}.

*{{citation

| last = Levin | first = Leonid | author-link = Leonid Levin

Line 122 ⟶ 119:

| title = Average case complete problems

| volume = 15

| year = 1986}}.

*{{citation

| last = Franco | first = John

| doi = 10.1016/0020-0190(86)90051-7

| issue = 2

| journal = Information Processing Letters

| pages = 103–106

| title = On the probabilistic performance of algorithms for the satisfiability problem

| volume = 23

| year = 1986}}..

*{{citation

| last1 = Flajolet | first1 = Philippe | author1-link = Philippe Flajolet

Line 208 ⟶ 214:

| title = A personal view of average-case complexity

| url = http://www-cse.ucsd.edu/~russell/average.ps}}.

*

*Paul E. Black, [https://web.archive.org/web/20090214175940/http://www.itl.nist.gov/div897/sqg/dads/HTML/theta.html "Θ"], in Dictionary of Algorithms and Data Structures[online]Paul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.Retrieved Feb. 20/09.

*Christos Papadimitriou (1994). Computational Complexity. Addison-Wesley.