Content deleted Content added
m WP:CHECKWIKI error fixes using AWB (10093) |
|||
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 two 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]].
Line 57:
The average-case analogue to NP-completeness is distNP-completeness. A distributional problem (L', D') is distNP-complete if (L', D') is in distNP and for every (L, D) in distNP, (L, D) is average-case reducible to (L', D').<ref name="ab09" />
An example of a distNP-complete problem is the Bounded Halting Problem, BH, defined as follows:
BH = {(M,x,1<sup>t</sup>) : M is a non-deterministic Turing machine that accepts x in ≤ t steps.}<ref name="ab09"/>
Line 66:
==Applicatons==
===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 O(n<sup>2</sup>), but an average-case running time of O(nlog(n)), where n is the length of the input to be sorted.<ref name="clrs">Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.</ref>
Line 81 ⟶ 82:
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 distNP-complete problem under the uniform distribution implies the existence of worst-case efficient algorithms for all problems in NP.<ref name="ff93">J. Feigenbaum and L. Fortnow, "Random-self-reducibility of complete sets," SIAM Journal on Computing, vol. 22, pp. 994-1005, 1993.</ref> In 2003, Bogdanov and Trevisan generalized this result to arbitrary non-adaptive reductions.<ref name="bog03">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.</ref> These results show that it is unlikely that any association can be made between average-case complexity and worst-case complexity via reductions.<ref name="bog06"/>
==
* [[Probabilistic analysis of algorithms]]
| |||