Incomputational complexity theory, theaverage-case complexity of analgorithm is the amount of somecomputational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted withworst-case complexity which considers the maximal complexity of the algorithm over all possible inputs.

There are three primary motivations for studying average-case complexity.^[1] 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 ascryptography andderandomization. Third, average-case complexity allows discriminating the most efficient algorithm in practice among algorithms of equivalent best case complexity (for instanceQuicksort).

Average-case analysis requires a notion of an "average" input to an algorithm, which leads to the problem of devising aprobability distribution over inputs. Alternatively, arandomized algorithm can be used. The analysis of such algorithms leads to the related notion of anexpected complexity.^[2]: 28

The average-case performance of algorithms has been studied since modern notions of computational efficiency were developed in the 1950s. Much of this initial work focused on problems for which worst-case polynomial time algorithms were already known.^[3] In 1973,Donald Knuth^[4] published Volume 3 of theArt of Computer Programming which extensively surveys average-case performance of algorithms for problems solvable in worst-case polynomial time, such as sorting and median-finding.

An efficient algorithm forNP-complete problems is generally characterized as one which runs in polynomial time for all inputs; this is equivalent to requiring efficient worst-case complexity. However, an algorithm which is inefficient on a "small" number of inputs may still be efficient for "most" inputs that occur in practice. Thus, it is desirable to study the properties of these algorithms where the average-case complexity may differ from the worst-case complexity and find methods to relate the two.

The fundamental notions of average-case complexity were developed byLeonid Levin in 1986 when he published a one-page paper^[5] defining average-case complexity and completeness while giving an example of a complete problem fordistNP, the average-case analogue ofNP.

The first task is to precisely define what is meant by an algorithm which is efficient "on average". An initial attempt might define an efficient average-case algorithm as one which runs in expected polynomial time over all possible inputs. Such a definition has various shortcomings; in particular, it is not robust to changes in the computational model. For example, suppose algorithmA runs in timet_A(x) on inputx and algorithmB runs in timet_A(x)² on inputx; that is,B is quadratically slower thanA. Intuitively, any definition of average-case efficiency should capture the idea thatA is efficient-on-average if and only ifB is efficient on-average. Suppose, however, that the inputs are drawn randomly from the uniform distribution of strings with lengthn, and thatA runs in timen² on all inputs except the string1ⁿ for whichA takes time2ⁿ. Then it can be easily checked that the expected running time ofA is polynomial but the expected running time ofB is exponential.^[3]

To create a more robust definition of average-case efficiency, it makes sense to allow an algorithmA to run longer than polynomial time on some inputs but the fraction of inputs on whichA requires larger and larger running time becomes smaller and smaller. This intuition is captured in the following formula for average polynomial running time, which balances the polynomial trade-off between running time and fraction of inputs:

${\displaystyle \underset{x{\in }_R{D}_n}{Pr}\left[t_A(x)\ge t\right]\le \frac{p(n)}{t^{ϵ}}}$

for everyn,t > 0 and polynomialp, wheret_A(x) denotes the running time of algorithmA on inputx, andε is a positive constant value.^[6] Alternatively, this can be written as

${\displaystyle E_{x{\in }_R{D}_n}\left[\frac{t_A(x{)}^{ϵ}}{n}\right]\le C}$

for some constantsC andε, wheren = |x|.^[7] In other words, an algorithmA has good average-case complexity if, after running fort_A(n) steps,A can solve all but a⁠n^c/(t_A(n))^ε⁠ fraction of inputs of lengthn, for someε,c > 0.^[3]

The next step is to define the "average" input to a particular problem. This is achieved by associating the inputs of each problem with a particular probability distribution. That is, an "average-case" problem consists of a languageL and an associated probability distributionD which forms the pair(L,D).^[7] The two most common classes of distributions which are allowed are:

1. Polynomial-time computable distributions (P-computable): these are distributions for which it is possible to compute the cumulative density of any given inputx. More formally, given a probability distributionμ and a stringx ∈ {0, 1}ⁿ it is possible to compute the value${\displaystyle \mu (x)=\sum _{y\in \{0,1{\}}^n:y\le x}Pr[y]}$ in polynomial time. This implies thatPr[x] is also computable in polynomial time.
2. Polynomial-time samplable distributions (P-samplable): these are distributions from which it is possible to draw random samples in polynomial time.

These two formulations, while similar, are not equivalent. If a distribution isP-computable it is alsoP-samplable, but the converse is not true ifP ≠P^#P.^[7]

A distributional problem(L,D) is in the complexity classAvgP if there is an efficient average-case algorithm forL, as defined above. The classAvgP is occasionally calleddistP in the literature.^[7]

A distributional problem(L,D) is in the complexity classdistNP ifL is inNP andD isP-computable. WhenL is inNP andD isP-samplable,(L,D) belongs tosampNP.^[7]

Together,AvgP anddistNP define the average-case analogues ofP andNP, respectively.^[7]

Let(L,D) and(L′,D′) be two distributional problems.(L,D) average-case reduces to(L′,D′) (written(L,D) ≤_AvgP (L′,D′)) if there is a functionf that for everyn, on inputx can be computed in time polynomial inn and

1. (Correctness)x ∈L if and only iff(x) ∈L′
2. (Domination) There are polynomialsp andm such that, for everyn andy,${\displaystyle \sum _{x:f(x)=y}{D}_n(x)\le p(n)D_{m(n)}^{\prime }(y)}$

The domination condition enforces the notion that if problem(L,D) is hard on average, then(L′,D′) is also hard on average. Intuitively, a reduction should provide a way to solve an instancex of problemL by computingf(x) and feeding the output to the algorithm which solvesL'. Without the domination condition, this may not be possible since the algorithm which solvesL in polynomial time on average may take super-polynomial time on a small number of inputs butf may map these inputs into a much larger set ofD' so that algorithmA' no longer runs in polynomial time on average. The domination condition only allows such strings to occur polynomially as often inD'.^[6]

The average-case analogue toNP-completeness isdistNP-completeness. A distributional problem(L′,D′) isdistNP-complete if(L′,D′) is indistNP and for every(L,D) indistNP,(L,D) is average-case reducible to(L′,D′).^[7]

An example of adistNP-complete problem is the BoundedHalting Problem,(BH,D) (for anyP-computableD) defined as follows:

${\displaystyle BH=\{(M,x,1^t):M\text{ is a non-deterministic Turing machine that accepts }x\text{ in}\le t\text{ steps}\}}$^[7]

In his original paper, Levin showed an example of a distributional tiling problem that is average-caseNP-complete.^[5] A survey of knowndistNP-complete problems is available online.^[6]

One area of active research involves finding newdistNP-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 bedistNP-complete unlessEXP =NEXP.^[8] (A flat distributionμ is one for which there exists anε > 0 such that for anyx,μ(x) ≤ 2^−|x|ε.) A result by Livne shows that all naturalNP-complete problems haveDistNP-complete versions.^[9] However, the goal of finding a natural distributional problem that isDistNP-complete has not yet been achieved.^[10]

As mentioned above, much early work relating to average-case complexity focused on problems for which polynomial-time algorithms already existed, such as sorting. For example, many sorting algorithms which utilize randomness, such asQuicksort, have a worst-case running time ofO(n²), but an average-case running time ofO(n log(n)), wheren is the length of the input to be sorted.^[2]

For most problems, average-case complexity analysis is undertaken to find efficient algorithms for a problem that is considered difficult in the worst-case. In cryptographic applications, however, the opposite is true: the worst-case complexity is irrelevant; we instead want a guarantee that the average-case complexity of every algorithm which "breaks" the cryptographic scheme is inefficient.^{[11][page needed]}

Thus, all secure cryptographic schemes rely on the existence ofone-way functions.^[3] Although the existence of one-way functions is still anopen problem, many candidate one-way functions are based on hard problems such asinteger factorization or computing thediscrete log. Note that it is not desirable for the candidate function to beNP-complete since this would only guarantee that there is likely no efficient algorithm for solving the problem in the worst case; what we actually want is a guarantee that no efficient algorithm can solve the problem over random inputs (i.e. the average case). In fact, both the integer factorization and discrete log problems are inNP ∩coNP, and are therefore not believed to beNP-complete.^[7] The fact that all of cryptography is predicated on the existence of average-case intractable problems inNP is one of the primary motivations for studying average-case complexity.

Yao's principle, from a 1978 paper byAndrew Yao, shows that for broad classes of computational problems, average-case complexity for a hard input distribution and adeterministic algorithm adapted to that distribution is the same thing as expected complexity for a fast randomized algorithm and its worst-case input.^[12]

In 1990, Impagliazzo and Levin showed that if there is an efficient average-case algorithm for adistNP-complete problem under the uniform distribution, then there is an average-case algorithm for every problem inNP under any polynomial-time samplable distribution.^[13] Applying this theory to natural distributional problems remains an outstanding open question.^[3]

In 1992, Ben-David et al. showed that if all languages indistNP have good-on-average decision algorithms, they also have good-on-average search algorithms. Further, they show that this conclusion holds under a weaker assumption: if every language inNP is easy on average for decision algorithms with respect to the uniform distribution, then it is also easy on average for search algorithms with respect to the uniform distribution.^[14] Thus, cryptographic one-way functions can exist only if there aredistNP problems over the uniform distribution that are hard on average for decision algorithms.

In 1993, Feigenbaum and Fortnow showed that it is not possible to prove, under non-adaptive random reductions, that the existence of a good-on-average algorithm for adistNP-complete problem under the uniform distribution implies the existence of worst-case efficient algorithms for all problems inNP.^[15] In 2003, Bogdanov and Trevisan generalized this result to arbitrary non-adaptive reductions.^[16] These results show that it is unlikely that any association can be made between average-case complexity and worst-case complexity via reductions.^[3]

• Probabilistic analysis of algorithms
• NP-complete problems
• Worst-case complexity
• Amortized analysis
• Best, worst and average case

Pedagogical presentations:

• Impagliazzo, R. (1995). "A personal view of average-case complexity".Proceedings of Structure in Complexity Theory. Tenth Annual IEEE Conference. IEEE Comput. Soc. Press. pp. 134–147.doi:10.1109/SCT.1995.514853.ISBN 978-0-8186-7052-7.
• Wang, Jie (1997). "Average-case computational complexity theory". In Hemaspaandra, Lane A.; Selman, Alan L. (eds.).Complexity Theory: Retrospective II(PDF). Vol. 2. Springer Science & Business Media. pp. 295–328.
• Goldreich, Oded (2011), Goldreich, Oded (ed.),"Average Case Complexity, Revisited"(PDF),Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, Lecture Notes in Computer Science, vol. 6650, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 422–450,doi:10.1007/978-3-642-22670-0_29,ISBN 978-3-642-22669-4{{citation}}: CS1 maint: work parameter with ISBN (link)
• Arora, Sanjeev; Barak, Boaz (2009). "18. Average case complexity: Levin's theory".Computational Complexity: A Modern Approach. Cambridge; New York: Cambridge University Press.

The literature of average case complexity includes the following work:

• Levin, Leonid (1986), "Average case complete problems",SIAM Journal on Computing,15 (1):285–286,doi:10.1137/0215020
• Franco, John (1986), "On the probabilistic performance of algorithms for the satisfiability problem",Information Processing Letters,23 (2):103–106,doi:10.1016/0020-0190(86)90051-7..
• Flajolet, Philippe;Vitter, J. S. (August 1987),Average-case analysis of algorithms and data structures, Tech. Report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France.
• Gurevich, Yuri;Shelah, Saharon (1987), "Expected computation time forHamiltonian path problem",SIAM Journal on Computing,16 (3):486–502,CiteSeerX 10.1.1.359.8982,doi:10.1137/0216034.
• Ben-David, Shai;Chor, Benny;Goldreich, Oded;Luby, Michael (1989), "On the theory of average case complexity",Proc. 21st Annual Symposium on Theory of Computing,Association for Computing Machinery, pp. 204–216.
• Gurevich, Yuri (1991), "Average case completeness",Journal of Computer and System Sciences,42 (3):346–398,doi:10.1016/0022-0000(91)90007-R,hdl:2027.42/29307. See also1989 draft.
• Selman, B.; Mitchell, D.; Levesque, H. (1992), "Hard and easy distributions of SAT problems",Proc. 10th National Conference on Artificial Intelligence, pp. 459–465.
• Schuler, Rainer; Yamakami, Tomoyuki (1992), "Structural average case complexity",Proc. Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 652, Springer-Verlag, pp. 128–139.
• Reischuk, Rüdiger; Schindelhauer, Christian (1993), "Precise average case complexity",Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science, pp. 650–661.
• Venkatesan, R.; Rajagopalan, S. (1992), "Average case intractability of matrix and Diophantine problems",Proc. 24th Annual Symposium on Theory of Computing,Association for Computing Machinery, pp. 632–642.
• Cox, Jim; Ericson, Lars; Mishra, Bud (1995),The average case complexity of multilevel syllogistic(PDF), Technical Report TR1995-711, New York University Computer Science Department.

• Randomized algorithms
• Analysis of algorithms

• CS1 maint: work parameter with ISBN
• Articles with short description
• Short description is different from Wikidata
• Wikipedia articles needing page number citations from May 2025