1647:-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
99:
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
134:
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,
1625:
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
42:
There are three primary motivations for studying average-case complexity. 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
1484:
78:
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. In 1973,
1708:
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. Thus, cryptographic one-way functions can exist only if there are
244:
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:
1730:. In 2003, Bogdanov and Trevisan generalized this result to arbitrary non-adaptive reductions. These results show that it is unlikely that any association can be made between average-case complexity and worst-case complexity via reductions.
1588:
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
610:
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
359:
1193:
745:
1930:
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,
1399:
504:
1702:
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
1962:
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.
1509:-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
100:
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.
1718:
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
51:. Third, average-case complexity allows discriminating the most efficient algorithm in practice among algorithms of equivalent best case complexity (for instance
43:
performance. Second, average-case complexity analysis provides tools and techniques to generate hard instances of problems which can be utilized in areas such as
2230:, in Dictionary of Algorithms and Data StructuresPaul E. Black, ed., U.S. National Institute of Standards and Technology. 17 December 2004.Retrieved Feb. 20/09.
87:
which extensively surveys average-case performance of algorithms for problems solvable in worst-case polynomial time, such as sorting and median-finding.
35:
is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with
1921:
J. Katz and Y. Lindell, Introduction to Modern
Cryptography (Chapman and Hall/Crc Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.
1912:
O. Goldreich, "Notes on Levin's theory of average-case complexity," Technical Report TR97-058, Electronic
Colloquium on Computational Complexity, 1997.
1789:
Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford (2009) . Introduction to
Algorithms (3rd ed.). MIT Press and McGraw-Hill.
1944:, 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.
251:
1693:
under any polynomial-time samplable distribution. Applying this theory to natural distributional problems remains an outstanding open question.
1891:
Y. Gurevich, "Complete and incomplete randomized NP problems", Proc. 28th Annual Symp. on Found. of
Computer Science, IEEE (1987), pp. 111β117.
107:
in 1986 when he published a one-page paper defining average-case complexity and completeness while giving an example of a complete problem for
1633:. Although the existence of one-way functions is still an open problem, many candidate one-way functions are based on hard problems such as
1739:
1085:
1817:
A. Bogdanov and L. Trevisan, "Average-Case
Complexity," Foundations and Trends in Theoretical Computer Science, Vol. 2, No 1 (2006) 1β106.
659:
2219:
2185:
2101:
2227:
1794:
1479:{\displaystyle BH=\{(M,x,1^{t}):M{\text{ is a non-deterministic Turing machine that accepts }}x{\text{ in}}\leq t{\text{ steps}}\}}
199:
is efficient on-average. Suppose, however, that the inputs are drawn randomly from the uniform distribution of strings with length
1953:
J. Feigenbaum and L. Fortnow, "Random-self-reducibility of complete sets," SIAM Journal on
Computing, vol. 22, pp. 994β1005, 1993.
1261:
no longer runs in polynomial time on average. The domination condition only allows such strings to occur polynomially as often in
2180:
2096:
2251:
1827:
24:
1724:-complete problem under the uniform distribution implies the existence of worst-case efficient algorithms for all problems in
2246:
1777:
O. Goldreich and S. Vadhan, Special issue on worst-case versus average-case complexity, Comput. Complex. 16, 325β330, 2007.
1900:
N. Livne, "All
Natural NP-Complete Problems Have Average-Case Complete Versions," Computational Complexity (2010) 19:477.
2034:, Tech. Report, Institut National de Recherche en Informatique et en Automatique, B.P. 105-78153 Le Chesnay Cedex France
1759:
58:
Average-case analysis requires a notion of an "average" input to an algorithm, which leads to the problem of devising a
84:
1667:-complete. The fact that all of cryptography is predicated on the existence of average-case intractable problems in
641:-computable): these are distributions for which it is possible to compute the cumulative density of any given input
1882:
S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, New York, NY, 2009.
413:
1856:
J. Wang, "Average-case computational complexity theory," Complexity Theory Retrospective II, pp. 295β328, 1997.
2048:
1687:-complete problem under the uniform distribution, then there is an average-case algorithm for every problem in
59:
2195:
2178:
Venkatesan, R.; Rajagopalan, S. (1992), "Average case intractability of matrix and Diophantine problems",
2060:
1842:
L. Levin, "Average case complete problems," SIAM Journal on Computing, vol. 15, no. 1, pp. 285β286, 1986.
760:-samplable): these are distributions from which it is possible to draw random samples in polynomial time.
1749:
1634:
36:
17:
1488:
In his original paper, Levin showed an example of a distributional tiling problem that is average-case
1978:
Franco, John (1986), "On the probabilistic performance of algorithms for the satisfiability problem",
1744:
63:
2065:
236:
To create a more robust definition of average-case efficiency, it makes sense to allow an algorithm
2209:
1626:
average-case complexity of every algorithm which "breaks" the cryptographic scheme is inefficient.
1754:
1681:
In 1990, Impagliazzo and Levin showed that if there is an efficient average-case algorithm for a
2148:
Selman, B.; Mitchell, D.; Levesque, H. (1992), "Hard and easy distributions of SAT problems",
2023:
1790:
1630:
1245:. Without the domination condition, this may not be possible since the algorithm which solves
1249:
in polynomial time on average may take super-polynomial time on a small number of inputs but
2130:
2122:
2070:
2011:
1987:
1222:
is also hard on average. Intuitively, a reduction should provide a way to solve an instance
1569:-complete versions. However, the goal of finding a natural distributional problem that is
114:
48:
1715:
problems over the uniform distribution that are hard on average for decision algorithms.
2168:
Reischuk, RΓΌdiger; Schindelhauer, Christian (1993), "Precise average case complexity",
2141:
2087:
2044:
2027:
777:
135:
it is not robust to changes in the computational model. For example, suppose algorithm
240:
to run longer than polynomial time on some inputs but the fraction of inputs on which
191:. Intuitively, any definition of average-case efficiency should capture the idea that
2240:
2162:, Lecture Notes in Computer Science, vol. 652, Springer-Verlag, pp. 128β139
2126:
2110:
2040:
1991:
2091:
1999:
1638:
104:
80:
44:
2158:
Schuler, Rainer; Yamakami, Tomoyuki (1992), "Structural average case complexity",
39:
which considers the maximal complexity of the algorithm over all possible inputs.
764:
These two formulations, while similar, are not equivalent. If a distribution is
91:
66:
can be used. The analysis of such algorithms leads to the related notion of an
2213:
2203:, Technical Report TR1995-711, New York University Computer Science Department
2083:
1941:
1901:
1590:
354:{\displaystyle \Pr _{x\in _{R}D_{n}}\left\leq {\frac {p(n)}{t^{\epsilon }}}}
52:
32:
2160:
Proc. Foundations of Software Technology and Theoretical Computer Science
2135:
2233:
Christos Papadimitriou (1994). Computational Complexity. Addison-Wesley.
1673:
is one of the primary motivations for studying average-case complexity.
1973:
The literature of average case complexity includes the following work:
2170:
Proc. 10th Annual Symposium on Theoretical Aspects of Computer Science
631:. The two most common classes of distributions which are allowed are:
1188:{\displaystyle \sum \limits _{x:f(x)=y}D_{n}(x)\leq p(n)D'_{m(n)}(y)}
103:
The fundamental notions of average-case complexity were developed by
2074:
2015:
407:
is a positive constant value. Alternatively, this can be written as
740:{\displaystyle \mu (x)=\sum \limits _{y\in \{0,1\}^{n}:y\leq x}\Pr}
225:. Then it can be easily checked that the expected running time of
1641:. Note that it is not desirable for the candidate function to be
1654:
1629:
Thus, all secure cryptographic schemes rely on the existence of
1524:
1516:
1451: is a non-deterministic Turing machine that accepts
1198:
The domination condition enforces the notion that if problem
1696:
In 1992, Ben-David et al. showed that if all languages in
2150:
Proc. 10th National Conference on Artificial Intelligence
2032:
Average-case analysis of algorithms and data structures
534:
has good average-case complexity if, after running for
2197:
The average case complexity of multilevel syllogistic
1402:
1241:
and feeding the output to the algorithm which solves
1088:
662:
416:
254:
2094:(1989), "On the theory of average case complexity",
816:
if there is an efficient average-case algorithm for
2181:Proc. 24th Annual Symposium on Theory of Computing
2097:Proc. 21st Annual Symposium on Theory of Computing
1478:
1372:-complete problem is the Bounded Halting Problem,
1187:
739:
645:. More formally, given a probability distribution
498:
353:
1503:One area of active research involves finding new
725:
256:
1253:may map these inputs into a much larger set of
229:is polynomial but the expected running time of
2194:Cox, Jim; Ericson, Lars; Mishra, Bud (1995),
499:{\displaystyle E_{x\in _{R}D_{n}}\left\leq C}
8:
1852:
1850:
1848:
1557:.) A result by Livne shows that all natural
1473:
1412:
776:-samplable, but the converse is not true if
702:
689:
615:and an associated probability distribution
16:"AvgP" redirects here. For other uses, see
2215:A personal view of average-case complexity
2002:(1986), "Average case complete problems",
942:Reductions between distributional problems
635:Polynomial-time computable distributions (
2134:
2064:
1902:https://doi.org/10.1007/s00037-010-0298-9
1838:
1836:
1617:is the length of the input to be sorted.
1468:
1457:
1449:
1434:
1401:
1158:
1124:
1093:
1087:
754:Polynomial-time samplable distributions (
705:
682:
661:
474:
458:
451:
439:
429:
421:
415:
343:
323:
294:
277:
267:
259:
253:
1500:-complete problems is available online.
1285:-completeness. A distributional problem
2115:Journal of Computer and System Sciences
2047:(1987), "Expected computation time for
1813:
1811:
1809:
1807:
1805:
1803:
1770:
1661:, and are therefore not believed to be
195:is efficient-on-average if and only if
1878:
1876:
1874:
1872:
1870:
1868:
1866:
1864:
1862:
1785:
1783:
1601:, but an average-case running time of
1032:can be computed in time polynomial in
751:is also computable in polynomial time.
747:in polynomial time. This implies that
395:denotes the running time of algorithm
2113:(1991), "Average case completeness",
1575:-complete has not yet been achieved.
926:define the average-case analogues of
7:
1740:Probabilistic analysis of algorithms
1593:, have a worst-case running time of
656:it is possible to compute the value
2220:University of California, San Diego
2186:Association for Computing Machinery
2102:Association for Computing Machinery
1090:
1066:(Domination) There are polynomials
679:
14:
1535:is one for which there exists an
130:Efficient average-case complexity
970:be two distributional problems.
213:on all inputs except the string
1830:. Vol. 3, Addison-Wesley, 1973.
1828:The Art of Computer Programming
530:. In other words, an algorithm
113:, the average-case analogue of
25:computational complexity theory
1980:Information Processing Letters
1440:
1415:
1182:
1176:
1168:
1162:
1151:
1145:
1136:
1130:
1109:
1103:
820:, as defined above. The class
734:
728:
672:
666:
471:
464:
335:
329:
306:
300:
62:over inputs. Alternatively, a
1:
1494:-complete. A survey of known
1351:is average-case reducible to
1273:The average-case analogue to
587:fraction of inputs of length
187:is quadratically slower than
2127:10.1016/0022-0000(91)90007-R
1992:10.1016/0020-0190(86)90051-7
1760:Best, worst and average case
847:is in the complexity class
810:is in the complexity class
90:An efficient algorithm for
85:Art of Computer Programming
2268:
83:published Volume 3 of the
15:
2053:SIAM Journal on Computing
2004:SIAM Journal on Computing
1210:is hard on average, then
1020:) if there is a function
835:A distributional problem
798:A distributional problem
2049:Hamiltonian path problem
1563:-complete problems have
1269:DistNP-complete problems
982:average-case reduces to
60:probability distribution
1531:. (A flat distribution
1394:) defined as follows:
826:is occasionally called
770:-computable it is also
29:average-case complexity
2252:Analysis of algorithms
1480:
1189:
741:
606:Distributional problem
500:
355:
74:History and background
2247:Randomized algorithms
1750:Worst-case complexity
1635:integer factorization
1481:
1190:
1074:such that, for every
742:
619:which forms the pair
501:
356:
37:worst-case complexity
18:avgp (disambiguation)
2210:Impagliazzo, Russell
1745:NP-complete problems
1400:
1086:
660:
554:can solve all but a
414:
252:
64:randomized algorithm
1175:
832:in the literature.
509:for some constants
68:expected complexity
2212:(April 17, 1995),
2188:, pp. 632β642
2172:, pp. 650β661
2152:, pp. 459β465
2104:, pp. 204β216
2024:Flajolet, Philippe
1755:Amortized analysis
1584:Sorting algorithms
1542:such that for any
1476:
1257:so that algorithm
1185:
1154:
1119:
873:-computable. When
737:
724:
496:
351:
284:
2082:Ben-David, Shai;
1637:or computing the
1631:one-way functions
1515:-complete unless
1471:
1460:
1452:
1279:-completeness is
1089:
678:
484:
349:
255:
2259:
2222:
2204:
2202:
2189:
2173:
2163:
2153:
2139:
2138:
2105:
2077:
2068:
2035:
2018:
1994:
1963:
1960:
1954:
1951:
1945:
1938:
1932:
1928:
1922:
1919:
1913:
1910:
1904:
1898:
1892:
1889:
1883:
1880:
1857:
1854:
1843:
1840:
1831:
1824:
1818:
1815:
1798:
1787:
1778:
1775:
1729:
1723:
1714:
1707:
1701:
1692:
1686:
1672:
1666:
1659:
1653:
1646:
1616:
1612:
1600:
1574:
1568:
1562:
1556:
1545:
1541:
1534:
1529:
1521:
1514:
1508:
1499:
1493:
1485:
1483:
1482:
1477:
1472:
1469:
1461:
1458:
1453:
1450:
1439:
1438:
1389:
1383:
1377:
1371:
1366:An example of a
1362:
1350:
1338:
1332:
1320:
1314:
1302:
1296:
1284:
1278:
1264:
1260:
1256:
1252:
1248:
1244:
1240:
1229:
1225:
1221:
1209:
1194:
1192:
1191:
1186:
1171:
1129:
1128:
1118:
1081:
1077:
1073:
1069:
1063:
1049:
1035:
1031:
1027:
1023:
1019:
993:
981:
969:
957:
938:, respectively.
937:
931:
925:
919:
910:
904:
892:
886:
882:
876:
872:
866:
862:
856:
852:
846:
831:
825:
819:
815:
809:
789:
782:
775:
769:
759:
750:
746:
744:
743:
738:
723:
710:
709:
655:
648:
644:
640:
630:
618:
614:
601:
590:
586:
585:
583:
582:
566:
563:
553:
549:
533:
529:
527:
516:
512:
505:
503:
502:
497:
489:
485:
480:
479:
478:
463:
462:
452:
446:
445:
444:
443:
434:
433:
406:
402:
398:
394:
378:
374:
360:
358:
357:
352:
350:
348:
347:
338:
324:
319:
315:
299:
298:
283:
282:
281:
272:
271:
243:
239:
233:is exponential.
232:
228:
224:
220:
216:
212:
206:
202:
198:
194:
190:
186:
182:
178:
162:
158:
154:
138:
119:
112:
96:
2267:
2266:
2262:
2261:
2260:
2258:
2257:
2256:
2237:
2236:
2226:Paul E. Black,
2208:
2200:
2193:
2177:
2167:
2157:
2147:
2109:
2088:Goldreich, Oded
2081:
2075:10.1137/0216034
2066:10.1.1.359.8982
2045:Shelah, Saharon
2039:
2030:(August 1987),
2022:
2016:10.1137/0215020
1998:
1977:
1971:
1969:Further reading
1966:
1961:
1957:
1952:
1948:
1939:
1935:
1929:
1925:
1920:
1916:
1911:
1907:
1899:
1895:
1890:
1886:
1881:
1860:
1855:
1846:
1841:
1834:
1825:
1821:
1816:
1801:
1788:
1781:
1776:
1772:
1768:
1736:
1725:
1719:
1710:
1703:
1697:
1688:
1682:
1679:
1668:
1662:
1655:
1648:
1642:
1623:
1614:
1602:
1594:
1586:
1581:
1570:
1564:
1558:
1547:
1543:
1536:
1532:
1525:
1517:
1510:
1504:
1495:
1489:
1430:
1398:
1397:
1385:
1375:
1373:
1367:
1352:
1340:
1334:
1322:
1316:
1304:
1298:
1286:
1280:
1274:
1271:
1262:
1258:
1254:
1250:
1246:
1242:
1231:
1227:
1223:
1211:
1199:
1120:
1084:
1083:
1079:
1075:
1071:
1067:
1051:
1050:if and only if
1041:
1033:
1029:
1025:
1024:that for every
1021:
1009:
995:
983:
971:
959:
947:
944:
933:
927:
921:
915:
906:
894:
888:
884:
878:
874:
868:
864:
858:
854:
848:
836:
827:
821:
817:
811:
799:
796:
794:AvgP and distNP
785:
778:
771:
765:
755:
748:
701:
658:
657:
650:
646:
642:
636:
620:
616:
612:
608:
592:
588:
576:
567:
564:
559:
558:
556:
555:
551:
543:
535:
531:
523:
518:
514:
510:
470:
454:
453:
447:
435:
425:
417:
412:
411:
404:
400:
396:
388:
380:
376:
375:and polynomial
365:
339:
325:
290:
289:
285:
273:
263:
250:
249:
241:
237:
230:
226:
222:
218:
214:
208:
204:
200:
196:
192:
188:
184:
180:
172:
164:
160:
156:
148:
140:
136:
132:
127:
115:
108:
92:
76:
49:derandomization
21:
12:
11:
5:
2265:
2263:
2255:
2254:
2249:
2239:
2238:
2235:
2234:
2231:
2224:
2206:
2191:
2175:
2165:
2155:
2145:
2121:(3): 346β398,
2111:Gurevich, Yuri
2107:
2079:
2059:(3): 486β502,
2041:Gurevich, Yuri
2037:
2020:
2010:(1): 285β286,
1996:
1986:(2): 103β106,
1970:
1967:
1965:
1964:
1955:
1946:
1940:S. Ben-David,
1933:
1923:
1914:
1905:
1893:
1884:
1858:
1844:
1832:
1819:
1799:
1779:
1769:
1767:
1764:
1763:
1762:
1757:
1752:
1747:
1742:
1735:
1732:
1678:
1675:
1622:
1619:
1585:
1582:
1580:
1577:
1475:
1467:
1464:
1456:
1448:
1445:
1442:
1437:
1433:
1429:
1426:
1423:
1420:
1417:
1414:
1411:
1408:
1405:
1321:and for every
1270:
1267:
1196:
1195:
1184:
1181:
1178:
1174:
1170:
1167:
1164:
1161:
1157:
1153:
1150:
1147:
1144:
1141:
1138:
1135:
1132:
1127:
1123:
1117:
1114:
1111:
1108:
1105:
1102:
1099:
1096:
1092:
1064:
1040:(Correctness)
1005:
943:
940:
795:
792:
762:
761:
752:
736:
733:
730:
727:
722:
719:
716:
713:
708:
704:
700:
697:
694:
691:
688:
685:
681:
677:
674:
671:
668:
665:
654:∈ {0, 1}
607:
604:
572:
539:
507:
506:
495:
492:
488:
483:
477:
473:
469:
466:
461:
457:
450:
442:
438:
432:
428:
424:
420:
384:
362:
361:
346:
342:
337:
334:
331:
328:
322:
318:
314:
311:
308:
305:
302:
297:
293:
288:
280:
276:
270:
266:
262:
258:
168:
159:and algorithm
144:
131:
128:
126:
123:
75:
72:
13:
10:
9:
6:
4:
3:
2:
2264:
2253:
2250:
2248:
2245:
2244:
2242:
2232:
2229:
2225:
2221:
2217:
2216:
2211:
2207:
2199:
2198:
2192:
2187:
2183:
2182:
2176:
2171:
2166:
2161:
2156:
2151:
2146:
2143:
2137:
2136:2027.42/29307
2132:
2128:
2124:
2120:
2116:
2112:
2108:
2103:
2099:
2098:
2093:
2092:Luby, Michael
2089:
2085:
2080:
2076:
2072:
2067:
2062:
2058:
2054:
2050:
2046:
2042:
2038:
2033:
2029:
2028:Vitter, J. S.
2025:
2021:
2017:
2013:
2009:
2005:
2001:
2000:Levin, Leonid
1997:
1993:
1989:
1985:
1981:
1976:
1975:
1974:
1968:
1959:
1956:
1950:
1947:
1943:
1937:
1934:
1927:
1924:
1918:
1915:
1909:
1906:
1903:
1897:
1894:
1888:
1885:
1879:
1877:
1875:
1873:
1871:
1869:
1867:
1865:
1863:
1859:
1853:
1851:
1849:
1845:
1839:
1837:
1833:
1829:
1823:
1820:
1814:
1812:
1810:
1808:
1806:
1804:
1800:
1796:
1795:0-262-03384-4
1792:
1786:
1784:
1780:
1774:
1771:
1765:
1761:
1758:
1756:
1753:
1751:
1748:
1746:
1743:
1741:
1738:
1737:
1733:
1731:
1728:
1722:
1716:
1713:
1706:
1700:
1694:
1691:
1685:
1677:Other results
1676:
1674:
1671:
1665:
1660:
1658:
1651:
1645:
1640:
1636:
1632:
1627:
1620:
1618:
1610:
1606:
1598:
1592:
1583:
1578:
1576:
1573:
1567:
1561:
1554:
1550:
1539:
1530:
1528:
1522:
1520:
1513:
1507:
1501:
1498:
1492:
1486:
1465:
1462:
1454:
1446:
1443:
1435:
1431:
1427:
1424:
1421:
1418:
1409:
1406:
1403:
1395:
1393:
1388:
1381:
1370:
1364:
1360:
1356:
1348:
1344:
1337:
1330:
1326:
1319:
1312:
1308:
1303:-complete if
1301:
1294:
1290:
1283:
1277:
1268:
1266:
1238:
1234:
1230:by computing
1219:
1215:
1207:
1203:
1179:
1172:
1165:
1159:
1155:
1148:
1142:
1139:
1133:
1125:
1121:
1115:
1112:
1106:
1100:
1097:
1094:
1065:
1062:
1058:
1054:
1048:
1044:
1039:
1038:
1037:
1017:
1013:
1008:
1003:
999:
991:
987:
979:
975:
967:
963:
955:
951:
941:
939:
936:
930:
924:
918:
912:
909:
902:
898:
891:
881:
871:
861:
851:
844:
840:
833:
830:
824:
814:
807:
803:
793:
791:
788:
783:
781:
774:
768:
758:
753:
731:
720:
717:
714:
711:
706:
698:
695:
692:
686:
683:
675:
669:
663:
653:
649:and a string
639:
634:
633:
632:
628:
624:
605:
603:
599:
595:
580:
575:
571:
562:
547:
542:
538:
526:
521:
493:
490:
486:
481:
475:
467:
459:
455:
448:
440:
436:
430:
426:
422:
418:
410:
409:
408:
392:
387:
383:
372:
368:
344:
340:
332:
326:
320:
316:
312:
309:
303:
295:
291:
286:
278:
274:
268:
264:
260:
248:
247:
246:
234:
211:
207:runs in time
176:
171:
167:
163:runs in time
152:
147:
143:
139:runs in time
129:
124:
122:
120:
118:
111:
106:
101:
98:
95:
88:
86:
82:
73:
71:
69:
65:
61:
56:
54:
50:
46:
40:
38:
34:
30:
26:
19:
2214:
2196:
2179:
2169:
2159:
2149:
2118:
2114:
2095:
2056:
2052:
2031:
2007:
2003:
1983:
1979:
1972:
1958:
1949:
1936:
1926:
1917:
1908:
1896:
1887:
1822:
1773:
1726:
1720:
1717:
1711:
1704:
1698:
1695:
1689:
1683:
1680:
1669:
1663:
1656:
1649:
1643:
1639:discrete log
1628:
1624:
1621:Cryptography
1608:
1604:
1596:
1587:
1579:Applications
1571:
1565:
1559:
1552:
1548:
1537:
1526:
1518:
1511:
1505:
1502:
1496:
1490:
1487:
1396:
1391:
1390:-computable
1386:
1379:
1368:
1365:
1358:
1354:
1346:
1342:
1335:
1328:
1324:
1317:
1310:
1306:
1299:
1292:
1288:
1281:
1275:
1272:
1236:
1232:
1217:
1213:
1205:
1201:
1197:
1060:
1056:
1052:
1046:
1042:
1015:
1011:
1006:
1001:
997:
989:
985:
977:
973:
965:
961:
953:
949:
945:
934:
928:
922:
916:
913:
907:
900:
896:
893:-samplable,
889:
879:
869:
859:
849:
842:
838:
834:
828:
822:
812:
805:
801:
797:
786:
779:
772:
766:
763:
756:
651:
637:
626:
622:
609:
597:
593:
578:
573:
569:
560:
545:
540:
536:
524:
519:
508:
390:
385:
381:
370:
366:
363:
235:
209:
174:
169:
165:
150:
145:
141:
133:
116:
109:
105:Leonid Levin
102:
93:
89:
81:Donald Knuth
77:
67:
57:
45:cryptography
41:
28:
22:
2140:. See also
2084:Chor, Benny
1470: steps
1226:of problem
1028:, on input
905:belongs to
591:, for some
221:takes time
203:, and that
183:; that is,
125:Definitions
2241:Categories
2142:1989 draft
1826:D. Knuth,
1766:References
914:Together,
364:for every
217:for which
2061:CiteSeerX
1591:Quicksort
1463:≤
1384:(for any
1140:≤
1091:∑
994:(written
718:≤
687:∈
680:∑
664:μ
491:≤
476:ϵ
427:∈
399:on input
345:ϵ
321:≤
310:≥
265:∈
179:on input
155:on input
97:-complete
53:Quicksort
33:algorithm
1734:See also
1613:, where
1459: in
1359:D′
1355:L′
1311:D′
1307:L′
1293:D′
1289:L′
1218:D′
1214:L′
1173:′
1061:L′
1016:D′
1012:L′
990:D′
986:L′
966:D′
962:L′
522:= |
517:, where
379:, where
1942:B. Chor
584:
557:
550:steps,
2063:
1793:
1721:distNP
1712:distNP
1699:distNP
1684:distNP
1572:DistNP
1566:DistNP
1540:> 0
1512:distNP
1506:distNP
1497:distNP
1369:distNP
1336:distNP
1318:distNP
1315:is in
1300:distNP
1282:distNP
923:distNP
908:sampNP
877:is in
857:is in
850:distNP
600:> 0
528:|
403:, and
373:> 0
110:distNP
31:of an
27:, the
2201:(PDF)
1931:1990.
1555:) β€ 2
829:distP
513:and
1791:ISBN
1657:coNP
1607:log(
1527:NEXP
1078:and
1070:and
1059:) β
1036:and
1007:AvgP
958:and
946:Let
932:and
920:and
917:AvgP
883:and
863:and
823:AvgP
813:AvgP
47:and
2228:"Ξ"
2131:hdl
2123:doi
2071:doi
2051:",
2012:doi
1988:doi
1519:EXP
1333:in
1297:is
1004:) β€
887:is
867:is
853:if
55:).
23:In
2243::
2218:,
2184:,
2129:,
2119:42
2117:,
2100:,
2090:;
2086:;
2069:,
2057:16
2055:,
2043:;
2026:;
2008:15
2006:,
1984:23
1982:,
1861:^
1847:^
1835:^
1802:^
1782:^
1727:NP
1705:NP
1690:NP
1670:NP
1664:NP
1652:β©
1650:NP
1644:NP
1611:))
1603:O(
1595:O(
1560:NP
1546:,
1523:=
1491:NP
1376:BH
1363:.
1357:,
1345:,
1339:,
1327:,
1309:,
1291:,
1276:NP
1265:.
1263:D'
1259:A'
1255:D'
1243:L'
1216:,
1204:,
1082:,
1045:β
1014:,
1000:,
988:,
976:,
964:,
935:NP
911:.
899:,
880:NP
860:NP
841:,
804:,
790:.
784:β
749:Pr
726:Pr
625:,
602:.
596:,
581:))
369:,
257:Pr
121:.
117:NP
94:NP
70:.
2223:.
2205:.
2190:.
2174:.
2164:.
2154:.
2144:.
2133::
2125::
2106:.
2078:.
2073::
2036:.
2019:.
2014::
1995:.
1990::
1797:.
1615:n
1609:n
1605:n
1599:)
1597:n
1553:x
1551:(
1549:ΞΌ
1544:x
1538:Ξ΅
1533:ΞΌ
1474:}
1466:t
1455:x
1447:M
1444::
1441:)
1436:t
1432:1
1428:,
1425:x
1422:,
1419:M
1416:(
1413:{
1410:=
1407:H
1404:B
1392:D
1387:P
1382:)
1380:D
1378:,
1374:(
1361:)
1353:(
1349:)
1347:D
1343:L
1341:(
1331:)
1329:D
1325:L
1323:(
1313:)
1305:(
1295:)
1287:(
1251:f
1247:L
1239:)
1237:x
1235:(
1233:f
1228:L
1224:x
1220:)
1212:(
1208:)
1206:D
1202:L
1200:(
1183:)
1180:y
1177:(
1169:)
1166:n
1163:(
1160:m
1156:D
1152:)
1149:n
1146:(
1143:p
1137:)
1134:x
1131:(
1126:n
1122:D
1116:y
1113:=
1110:)
1107:x
1104:(
1101:f
1098::
1095:x
1080:y
1076:n
1072:m
1068:p
1057:x
1055:(
1053:f
1047:L
1043:x
1034:n
1030:x
1026:n
1022:f
1018:)
1010:(
1002:D
998:L
996:(
992:)
984:(
980:)
978:D
974:L
972:(
968:)
960:(
956:)
954:D
952:,
950:L
948:(
929:P
903:)
901:D
897:L
895:(
890:P
885:D
875:L
870:P
865:D
855:L
845:)
843:D
839:L
837:(
818:L
808:)
806:D
802:L
800:(
787:P
780:P
773:P
767:P
757:P
735:]
732:y
729:[
721:x
715:y
712::
707:n
703:}
699:1
696:,
693:0
690:{
684:y
676:=
673:)
670:x
667:(
652:x
647:ΞΌ
643:x
638:P
629:)
627:D
623:L
621:(
617:D
613:L
598:c
594:Ξ΅
589:n
579:n
577:(
574:A
570:t
568:(
565:/
561:n
552:A
548:)
546:n
544:(
541:A
537:t
532:A
525:x
520:n
515:Ξ΅
511:C
494:C
487:]
482:n
472:)
468:x
465:(
460:A
456:t
449:[
441:n
437:D
431:R
423:x
419:E
405:Ξ΅
401:x
397:A
393:)
391:x
389:(
386:A
382:t
377:p
371:t
367:n
341:t
336:)
333:n
330:(
327:p
317:]
313:t
307:)
304:x
301:(
296:A
292:t
287:[
279:n
275:D
269:R
261:x
242:A
238:A
231:B
227:A
223:2
219:A
215:1
210:n
205:A
201:n
197:B
193:A
189:A
185:B
181:x
177:)
175:x
173:(
170:A
166:t
161:B
157:x
153:)
151:x
149:(
146:A
142:t
137:A
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.