Английская Википедия:Average-case complexity
Шаблон:Redirect 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.[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 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).
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.[2]Шаблон:Rp
History and background
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 the Art 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 for [[NP-complete|Шаблон:Math-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 by Leonid 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 for Шаблон:Math, the average-case analogue of [[NP (complexity)|Шаблон:Math]].
Definitions
Efficient average-case complexity
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 algorithm Шаблон:Mvar runs in time Шаблон:Math on input Шаблон:Mvar and algorithm Шаблон:Mvar runs in time Шаблон:Math on input Шаблон:Mvar; that is, Шаблон:Mvar is quadratically slower than Шаблон:Mvar. Intuitively, any definition of average-case efficiency should capture the idea that Шаблон:Mvar is efficient-on-average if and only if Шаблон:Mvar is efficient on-average. Suppose, however, that the inputs are drawn randomly from the uniform distribution of strings with length Шаблон:Mvar, and that Шаблон:Mvar runs in time Шаблон:Math on all inputs except the string Шаблон:Math for which Шаблон:Mvar takes time Шаблон:Math. Then it can be easily checked that the expected running time of Шаблон:Mvar is polynomial but the expected running time of Шаблон:Mvar is exponential.[3]
To create a more robust definition of average-case efficiency, it makes sense to allow an algorithm Шаблон:Mvar to run longer than polynomial time on some inputs but the fraction of inputs on which Шаблон:Mvar 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:
- <math>
\Pr_{x \in_R D_n} \left[t_A(x) \geq t \right] \leq \frac{p(n)}{t^\epsilon} </math>
for every Шаблон:Math and polynomial Шаблон:Mvar, where Шаблон:Math denotes the running time of algorithm Шаблон:Mvar on input Шаблон:Mvar, and Шаблон:Mvar is a positive constant value.[6] Alternatively, this can be written as
- <math>
E_{x \in_R D_n} \left[ \frac{t_{A}(x)^{\epsilon}}{n} \right] \leq C </math>
for some constants Шаблон:Mvar and Шаблон:Mvar, where Шаблон:Math.[7] In other words, an algorithm Шаблон:Mvar has good average-case complexity if, after running for Шаблон:Math steps, Шаблон:Mvar can solve all but a Шаблон:Math fraction of inputs of length Шаблон:Mvar, for some Шаблон:Math.[3]
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 Шаблон:Mvar and an associated probability distribution Шаблон:Mvar which forms the pair Шаблон:Math.[7] The two most common classes of distributions which are allowed are:
- Polynomial-time computable distributions (Шаблон:Math-computable): these are distributions for which it is possible to compute the cumulative density of any given input Шаблон:Mvar. More formally, given a probability distribution Шаблон:Mvar and a string Шаблон:Math 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 Шаблон:Math is also computable in polynomial time.
- Polynomial-time samplable distributions (Шаблон:Math-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 is Шаблон:Math-computable it is also Шаблон:Math-samplable, but the converse is not true if [[P (complexity)|Шаблон:Math]] ≠ Шаблон:Math.[7]
AvgP and distNP
A distributional problem Шаблон:Math is in the complexity class Шаблон:Math if there is an efficient average-case algorithm for Шаблон:Mvar, as defined above. The class Шаблон:Math is occasionally called Шаблон:Math in the literature.[7]
A distributional problem Шаблон:Math is in the complexity class Шаблон:Math if Шаблон:Mvar is in Шаблон:Math and Шаблон:Mvar is Шаблон:Math-computable. When Шаблон:Mvar is in Шаблон:Math and Шаблон:Mvar is Шаблон:Math-samplable, Шаблон:Math belongs to Шаблон:Math.[7]
Together, Шаблон:Math and Шаблон:Math define the average-case analogues of Шаблон:Math and Шаблон:Math, respectively.[7]
Reductions between distributional problems
Let Шаблон:Math and Шаблон:Math be two distributional problems. Шаблон:Math average-case reduces to Шаблон:Math (written Шаблон:Math) if there is a function Шаблон:Mvar that for every Шаблон:Mvar, on input Шаблон:Mvar can be computed in time polynomial in Шаблон:Mvar and
- (Correctness) Шаблон:Math if and only if Шаблон:Math
- (Domination) There are polynomials Шаблон:Mvar and Шаблон:Mvar such that, for every Шаблон:Mvar and Шаблон:Mvar, <math>\sum\limits_{x: f(x) = y} D_n(x) \leq p(n)D'_{m(n)}(y)</math>
The domination condition enforces the notion that if problem Шаблон:Math is hard on average, then Шаблон:Math is also hard on average. Intuitively, a reduction should provide a way to solve an instance Шаблон:Mvar of problem Шаблон:Mvar by computing Шаблон:Math and feeding the output to the algorithm which solves Шаблон:Mvar. Without the domination condition, this may not be possible since the algorithm which solves Шаблон:Mvar in polynomial time on average may take super-polynomial time on a small number of inputs but Шаблон:Mvar may map these inputs into a much larger set of Шаблон:Mvar so that algorithm Шаблон:Mvar no longer runs in polynomial time on average. The domination condition only allows such strings to occur polynomially as often in Шаблон:Mvar.[6]
DistNP-complete problems
The average-case analogue to Шаблон:Math-completeness is Шаблон:Math-completeness. A distributional problem Шаблон:Math is Шаблон:Math-complete if Шаблон:Math is in Шаблон:Math and for every Шаблон:Math in Шаблон:Math, Шаблон:Math is average-case reducible to Шаблон:Math.[7]
An example of a Шаблон:Math-complete problem is the Bounded Halting Problem, Шаблон:Mvar, defined as follows:
<math>BH = \{(M, x, 1^t) : M \text{ is a non-deterministic Turing machine that accepts } x \text{ in} \leq t \text{ steps}\}</math>[7]
In his original paper, Levin showed an example of a distributional tiling problem that is average-case Шаблон:Math-complete.[5] A survey of known Шаблон:Math-complete problems is available online.[6]
One area of active research involves finding new Шаблон:Math-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-complete unless [[EXP|Шаблон:Math]] = [[NEXP|Шаблон:Math]].[8] (A flat distribution Шаблон:Mvar is one for which there exists an Шаблон:Math such that for any Шаблон:Mvar, Шаблон:Math.) A result by Livne shows that all natural Шаблон:Math-complete problems have Шаблон:Math-complete versions.[9] However, the goal of finding a natural distributional problem that is Шаблон:Math-complete has not yet been achieved.[10]
Applications
Sorting algorithms
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 as Quicksort, have a worst-case running time of Шаблон:Math, but an average-case running time of Шаблон:Math, where Шаблон:Mvar is the length of the input to be sorted.[2]
Cryptography
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]
Thus, all secure cryptographic schemes rely on the existence of one-way functions.[3] Although the existence of one-way functions is still an open problem, many candidate one-way functions are based on hard problems such as integer factorization or computing the discrete log. Note that it is not desirable for the candidate function to be Шаблон:Math-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 Шаблон:Math[[coNP|Шаблон:Math]], and are therefore not believed to be Шаблон:Math-complete.[7] The fact that all of cryptography is predicated on the existence of average-case intractable problems in Шаблон:Math is one of the primary motivations for studying average-case complexity.
Other results
In 1990, Impagliazzo and Levin showed that if there is an efficient average-case algorithm for a Шаблон:Math-complete problem under the uniform distribution, then there is an average-case algorithm for every problem in Шаблон:Math under any polynomial-time samplable distribution.[12] Applying this theory to natural distributional problems remains an outstanding open question.[3]
In 1992, Ben-David et al. showed that if all languages in Шаблон:Math 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 in Шаблон:Math 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.[13] Thus, cryptographic one-way functions can exist only if there are Шаблон:Math 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 a Шаблон:Math-complete problem under the uniform distribution implies the existence of worst-case efficient algorithms for all problems in Шаблон:Math.[14] In 2003, Bogdanov and Trevisan generalized this result to arbitrary non-adaptive reductions.[15] These results show that it is unlikely that any association can be made between average-case complexity and worst-case complexity via reductions.[3]
See also
- Probabilistic analysis of algorithms
- NP-complete problems
- Worst-case complexity
- Amortized analysis
- Best, worst and average case
References
Further reading
The literature of average case complexity includes the following work:
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation. See also 1989 draft.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Шаблон:Citation.
- Paul E. Black, "Θ", 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.
- ↑ O. Goldreich and S. Vadhan, Special issue on worst-case versus average-case complexity, Comput. Complex. 16, 325–330, 2007.
- ↑ 2,0 2,1 Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. Шаблон:ISBN.
- ↑ 3,0 3,1 3,2 3,3 3,4 3,5 A. Bogdanov and L. Trevisan, "Average-Case Complexity," Foundations and Trends in Theoretical Computer Science, Vol. 2, No 1 (2006) 1–106.
- ↑ D. Knuth, The Art of Computer Programming. Vol. 3, Addison-Wesley, 1973.
- ↑ 5,0 5,1 L. Levin, "Average case complete problems," SIAM Journal on Computing, vol. 15, no. 1, pp. 285–286, 1986.
- ↑ 6,0 6,1 6,2 J. Wang, "Average-case computational complexity theory," Complexity Theory Retrospective II, pp. 295–328, 1997.
- ↑ 7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 7,8 S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009.
- ↑ Y. Gurevich, "Complete and incomplete randomized NP problems", Proc. 28th Annual Symp. on Found. of Computer Science, IEEE (1987), pp. 111–117.
- ↑ 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
- ↑ O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic Colloquium on Computational Complexity, 1997.
- ↑ J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.
- ↑ R. Impagliazzo and L. Levin, "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random," in Proceedings of the 31st IEEE Sympo- sium on Foundations of Computer Science, pp. 812–821, 1990.
- ↑ S. Ben-David, B. Chor, O. Goldreich, and M. Luby, "On the theory of average case complexity," Journal of Computer and System Sciences, vol. 44, no. 2, pp. 193–219, 1992.
- ↑ J. Feigenbaum and L. Fortnow, "Random-self-reducibility of complete sets," SIAM Journal on Computing, vol. 22, pp. 994–1005, 1993.
- ↑ A. Bogdanov and L. Trevisan, "On worst-case to average-case reductions for NP problems," in Proceedings of the 44th IEEE Symposium on Foundations of Computer Science, pp. 308–317, 2003.