Average-case complexity: Difference between revisions

Revision as of 09:35, 21 June 2014

Revision as of 09:03, 16 July 2014

Line 1:

'''Average-case complexity''' is a subfield of [[computational complexity theory]] that studies the complexity of [[algorithms]] over inputs drawn randomly from a particular [[probability distribution]]. 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. Goldreich and S. Vadhan, Special issue on worst-case versus average-case complexity, Comput. Complex. 16, 325-330, 2007.</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 based case complexity (for instance [[Quicksort#Formal analysis|Quicksort]]).

==History and Background==

Line 23:

</math>

for every n, t, &epsilon;ε > 0 and polynomial p, where t_A(x) denotes the running time of algorithm A on input x.<ref name="wangsurvey">J. Wang, "Average-case computational complexity theory," Complexity Theory Retrospective II, pp. 295-328, 1997.</ref> Alternatively, this can be written as

<math>

Line 29:

</math>

for some constant C, where n = |x|.<ref name="ab09">S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009.</ref> In other words, an algorithm A has good average-case complexity if, after running for t_A(n) steps, A can solve all but a <math>\frac{n^c}{(t_A(n))^{\epsilon}}</math> fraction of inputs of length n, for some &epsilon;ε, c > 0.<ref name="bog06"/>

===Distributional Problem===

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 language L and an associated probability distribution D which forms the pair (L, D).<ref name="ab09"/> The two most common classes of distributions which are allowed are:

#Polynomial-time computable distributions (P-computable): these are distributions for which it is possible to compute the cumulative density of any given input x. More formally, given a probability distribution &mu;μ and a string x &isin;∈ {0, 1}ⁿ it is possible to compute the value <math>\mu(x) = \sum\limits_{y \in \{0, 1\}^n : y \leq x} \Pr[y]</math> in polynomial time. This implies that Pr[x] is also computable in polynomial time.

#Polynomial-time samplable distributions (P-samplable): these are distributions from which it is possible to draw random samples in polynomial time.

Line 47:

==Reductions Between Distributional Problems==

Let (L,D) and (L',D') be two distributional problems. (L, D) average-case reduces to (L', D') (written (L, D) &le;≤_AvgP (L', D')) if there is a function f that for every n, on input x can be computed in time polynomial in n and

#(Correctness) x &isin;∈ L if and only if f(x) &isin;∈ L'

#(Domination) There are polynomials p and m such that, for every n and y, <math>\sum\limits_{x: f(x) = y} D_n(x) \leq p(n)D'_{m(n)}(y)</math>

Line 59:

An example of a distNP-complete problem is the Bounded Halting Problem, BH, defined as follows:

BH = {(M,x,1^t) : M is a non-deterministic Turing machine that accepts x in &le;≤ t steps.}<ref name="ab09"/>

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

One area of active research involves finding new 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 distNP-complete unless [[EXP]] = [[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 &mu;μ is one for which there exists an &epsilon;ε > 0 such that for any x, &mu;μ(x) &le;≤ 2^{-|x|^&epsilon;ε}.) A result by Livne shows that all natural NP problems have DistNP-complete versions.<ref name="livne06">N. Livne, "All Natural NPC Problems Have Average-Case Complete Versions," Computational Complexity, to appear. Preliminary version in ECCC, TR06-122, 2006.</ref> However, the goal of finding a natural distributional problem that is DistNP-complete has not yet been achieved.<ref name="gol97">O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic Colloquium on Computational Complexity, 1997.</ref>

==Applicatons==

Line 73:

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.<ref name="katz07">J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.</ref>

Thus, all secure cryptographic schemes rely on the existence of [[one-way functions]].<ref name="bog06"/> Although the existence of one-way functions is still an open problem, many candidate one-way functions are based on NP-hard problems such as [[integer factorization]] or computing the [[discrete log]]. Note that it is not desirable for the candidate function to be NP-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 in NP &cap;∩ [[coNP]], and are therefore not believed to be NP-complete.<ref name="ab09"/> The fact that all of cryptography is predicated on the existence of average-case intractable problems in NP is one of the primary motivations for studying average-case complexity.

==Other Results==

Line 84:

==See also==

* [[Probabilistic analysis of algorithms]]

*[[NP-complete problems]]

*[[Worst-case complexity]]

==LiteratureReferences==

{{Reflist|30em}}<!--added above categories/infobox footers by script-assisted edit-->

==Further reading==

The literature of average case complexity includes the following work:

*{{citation

Line 191 ⟶ 195:

*Paul E. Black, [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.

==See also==

*[[NP-complete problems]]

*[[Worst-case complexity]]

==References==

{{Reflist}}<!--added above categories/infobox footers by script-assisted edit-->

[[Category:Probabilistic complexity theory]]