772:
804:
660:, the problem of determining whether a polynomial is identically equal to the zero polynomial, when you have access to the value of the polynomial for any given input, but not to the coefficients. In other words, is there an assignment of values to the variables such that when a nonzero polynomial is evaluated on these values, the result is nonzero? It suffices to choose each variable's value uniformly at random from a finite subset of at least
477:. For example, if one defined the class with the restriction that the algorithm can be wrong with probability at most 1/2, this would result in the same class of problems. The error probability does not even have to be constant: the same class of problems is defined by allowing error as high as 1/2 −
1951:
Studies in
Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi
1395:
The machine is simulated, and the oracle answers (that are not already fixed) are fixed step-by-step. There is at most one oracle query per deterministic computation step. For the relativized NP oracle, if possible fix the output to be yes by choosing a computation path and fixing the answers of
1471:
by most experts of the field. Such generators could replace true random numbers in any polynomial-time randomized algorithm, producing indistinguishable results. The conjecture that these generators exist implies that randomness does not give additional computational power to polynomial time
1416:, linear time suffices, even for function problems (if given a function oracle and linear output size) and with exponentially small (with linear exponent) error probability. Also, this construction is effective in that given an arbitrary oracle A we can arrange the oracle B to have
1605:
489:
is the length of input. This flexibility in the choice of error probability is based on the idea of running an error-prone algorithm many times, and using the majority result of the runs to obtain a more accurate algorithm. The chance that the majority of the runs are wrong
1121:
algorithm operating on inputs of bounded length can be derandomized into a deterministic algorithm using a fixed string of random bits. Finding this string may be expensive, however. Some weak separation results for Monte Carlo time classes were proven by
762:
contains probabilistic algorithms that are always correct and have expected polynomial running time. This is weaker than saying it is a polynomial time algorithm, since it may run for super-polynomial time, but with very low probability.
465:
corresponds to the output of the random coin flips that the probabilistic Turing machine would have made. For some applications this definition is preferable since it does not mention probabilistic Turing machines.
1743:
1051:
1247:
1532:
559:
752:
which is a randomized algorithm which either outputs the correct answer, or outputs "fail" with low probability. Las Vegas algorithms with polynomial bound running times are used to define the class
1323:
453:
385:
1396:
the base oracle; otherwise no fixing is necessary, and either way there is at most 1 answer of the base oracle per step. Since there are 2 steps, the lemma follows.
1331:(relativized) complete problem, the oracle will give correct answers with high probability if queried with the problem instance followed by a random string of length
469:
In practice, an error probability of 1/3 might not be acceptable, however, the choice of 1/3 in the definition is arbitrary. Modifying the definition to use any
17:
86:, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.
1351:
fix oracle answers (see lemma below) to fix the instance output. Next, provide the instance outputs for queries consisting of the instance followed by
565:
2200:
1672:
1000:
1600:{\displaystyle {\textsf {i.o.-SUBEXP}}=\bigcap \nolimits _{\varepsilon >0}{\textsf {i.o.-DTIME}}\left(2^{n^{\varepsilon }}\right).}
2597:
1455:), one would fix the answers in the relativized E computation to a special nonanswer, thus ensuring that no fake answers are given.
1194:
517:
216:
On any given run of the algorithm, it has a probability of at most 1/3 of giving the wrong answer, whether the answer is YES or NO.
1877:
2105:; Verbeek, Rutger (1987a). "Randomness, provability, and the separation of Monte Carlo time and space". In Börger, Egon (ed.).
1256:
2169:
2562:
2091:
2064:
2193:
33:
1818:
Madhu Sudan and Shien Jin Ong. Massachusetts
Institute of Technology: 6.841/18.405J Advanced Complexity Theory:
1464:
2127:"On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes"
1880:; Gill, John (1981), "Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1",
994:
234:
49:
291:
is required to run for polynomial time on all inputs, regardless of the outcome of the random coin flips.
2186:
657:
2578:
2385:
1786:
2567:
2071:
Pages 257–259 of section 11.3: Random
Sources. Pages 269–271 of section 11.4: Circuit complexity.
2044:
1846:
843:
73:
2521:
2052:
417:
349:
2516:
2511:
2161:
737:
635:
found a deterministic polynomial-time algorithm for this problem, thus showing that it is in
470:
2506:
1819:
1631:
1619:
1096:
986:
741:
1404:), it is possible to do the construction while leaving enough strings for the relativized
1377:
Given a problem (specifically, an oracle machine code and time constraint) in relativized
8:
1653:
749:
1914:
Heller, Hans (1986), "On relativized exponential and probabilistic complexity classes",
748:
have Monte Carlo algorithms with polynomial bounded running time. This is compared to a
1998:
1492:
is in some sense equivalent to the existence of strong pseudorandom number generators.
616:
1943:
1928:
2526:
2143:
2126:
2087:
2080:
2060:
1897:
1832:
1495:
973:. It is not known whether those two are strict subsets, since we don't even know if
491:
2002:
2490:
2380:
2302:
2209:
2138:
2110:
2028:
1990:
1955:
1923:
1889:
1806:
1773:
1443:
859:
776:
754:
689:
624:
283:
45:
877:) is not any more powerful than the machine without this extra power. In symbols,
771:
2485:
2475:
2432:
2422:
2415:
2405:
2395:
2353:
2348:
2343:
2327:
2307:
2285:
2280:
2275:
2263:
2258:
2253:
2248:
2173:
2151:
Arora, Sanjeev; Boaz Barak (2009). "Computational
Complexity: A Modern Approach".
2122:
2102:
1959:
1954:. Lecture Notes in Computer Science. Vol. 6650. Springer. pp. 191–232.
1859:
1766:
1518:
1104:
969:
955:
942:
908:
894:
828:
812:
788:
780:
648:
473:
between 0 and 1/2 (exclusive) in place of 1/3 would not change the resulting set
53:
2109:. Lecture Notes in Computer Science. Vol. 270. Springer. pp. 189–207.
803:
2480:
2368:
2290:
2243:
2075:
1864:
Proceedings of the
Nineteenth Annual IEEE Symposium on Foundations of Computing
1662:
1328:
874:
808:
792:
685:
607:
495:
82:
2114:
2591:
2166:
1901:
1657:
1507:
1499:
1163:
702:
928:, which is considered unlikely since it would imply practical solutions for
505:
2025:
Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of
Computing
1646:; however, note that the exponential-time hierarchy is usually conjectured
709:, or allowing computation paths to have different lengths, gives the class
632:
628:
611:
481:
on the one hand, or requiring error as small as 2 on the other hand, where
2032:
2358:
2268:
1146:
Relative to oracles, we know that there exist oracles A and B, such that
929:
57:
587:. The number of such problems is decreasing, and it is conjectured that
2470:
2295:
2043:
Valentine
Kabanets (2003). "CMPT 710 – Complexity Theory: Lecture 16".
1994:
1503:
1468:
1138:
The class BPP is closed under complementation, union and intersection.
2465:
2178:
1738:{\displaystyle {\mathsf {E}}={\mathsf {DTIME}}\left(2^{O(n)}\right),}
1973:
Babai, László; Fortnow, Lance; Nisan, Noam; Wigderson, Avi (1993). "
1893:
1630:
if the exponential-time hierarchy, which is defined in terms of the
298:
can be defined using only deterministic Turing machines. A language
2460:
2455:
2400:
2223:
206:
if there is an algorithm for it that has the following properties:
2023:
if E requires exponential circuits: Derandomizing the XOR Lemma".
1622:
algorithms for infinitely many input sizes. They also showed that
2450:
1512:
1327:), which can be iteratively constructed as follows. For a fixed
1046:{\displaystyle {\mathsf {BPP}}\subseteq \Sigma _{2}\cap \Pi _{2}}
729:
598:
For a long time, one of the most famous problems known to be in
2557:
2552:
2427:
2410:
1113:
903:
832:
824:
796:
1355:-length string, and then treat output for queries of length ≤(
1242:{\displaystyle {\mathsf {BPP}}={\mathsf {EXP}}^{\mathsf {NP}}}
676:
If the access to randomness is removed from the definition of
2547:
2542:
2363:
1383:, for every partially constructed oracle and input of length
816:
684:. In the definition of the class, if we replace the ordinary
554:{\displaystyle {\mathsf {P}}{\overset {?}{=}}{\mathsf {BPP}}}
1117:. Indeed, as a consequence of the proof of this fact, every
2375:
2233:
775:
BPP in relation to other probabilistic complexity classes (
1972:
1387:, the output can be fixed by specifying 2 oracle answers.
68:
classes of problems, meaning most problems of interest in
2390:
2322:
2317:
2238:
2228:
2107:
Computation Theory and Logic, In Memory of Dieter Rödding
1780:
784:
694:
799:. It is unknown if any of these containments are strict.
1410:
answers. Also, we can ensure that for the relativized
262:
outputs 1 with probability greater than or equal to 2/3
2051:
1675:
1535:
1259:
1197:
1003:
744:
which is likely to be correct. Problems in the class
520:
420:
352:
210:
It is allowed to flip coins and make random decisions
507:
277:
outputs 1 with probability less than or equal to 1/3
1820:
Lecture 6: Randomized
Algorithms, Properties of BPP
1318:{\displaystyle {\mathsf {P<NP<BPP=EXP=NEXP}}}
664:values to achieve bounded error probability, where
2079:
1862:(1978). "Two theorems on random polynomial time".
1737:
1599:
1317:
1241:
1045:
766:
579:. However, many problems have been known to be in
553:
447:
379:
76:that can be run quickly on real modern machines.
2121:
2101:
1347:=1. For every instance of the problem of length
1127:
1123:
1103:can be determined by a family of polynomial-size
727:, and it is contained in its quantum counterpart
2589:
2098:Section 10.2.1: The class BPP, pp. 336–339.
2015:Russell Impagliazzo and Avi Wigderson (1997). "
1363:as fixed, and proceed with instances of length
1343:is an appropriate small constant). Start with
2074:
1858:
2194:
2162:Princeton CS 597E: Derandomization paper list
566:(more unsolved problems in computer science)
1977:has subexponential time simulations unless
1876:
1400:The lemma ensures that (for a large enough
807:Inclusions of complexity classes including
38:bounded-error probabilistic polynomial time
2201:
2187:
1099:states that membership in any language in
213:It is guaranteed to run in polynomial time
2142:
2082:Introduction to the Theory of Computation
1941:
1927:
1564:
1538:
306:if and only if there exists a polynomial
1807:CMPT 710 - Complexity Theory: Lecture 16
985:is contained in the second level of the
802:
770:
668:is the total degree of the polynomial.
14:
2590:
2208:
1913:
1700:
1697:
1694:
1691:
1688:
1678:
1310:
1307:
1304:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1233:
1230:
1223:
1220:
1217:
1206:
1203:
1200:
1012:
1009:
1006:
546:
543:
540:
523:
321:runs for polynomial time on all inputs
247:runs for polynomial time on all inputs
18:Bounded-error probabilistic polynomial
2182:
1484:. More strongly, the assumption that
1133:
642:An important example of a problem in
1966:
1614:, which stands for infinitely often
898:is unknown: it is not known whether
508:Unsolved problem in computer science
1833:"Complexity Zoo:B - Complexity Zoo"
1547:
30:
24:
1458:
1034:
1021:
671:
60:bounded by 1/3 for all instances.
25:
2609:
2563:Probabilistically checkable proof
2155:
1189:There is even an oracle in which
1141:
989:and therefore it is contained in
310:and deterministic Turing machine
2598:Probabilistic complexity classes
2167:Harvard CS 225: Pseudorandomness
2059:(1st ed.). Addison Wesley.
1463:The existence of certain strong
866:machine with the power to solve
36:, a branch of computer science,
2009:
1618:, contains problems which have
1128:Karpinski & Verbeek (1987b)
1124:Karpinski & Verbeek (1987a)
767:Complexity-theoretic properties
461:In this definition, the string
389:is greater than or equal to 2/3
34:computational complexity theory
1935:
1907:
1870:
1852:
1839:
1825:
1812:
1799:
1748:has circuit complexity 2 then
1723:
1717:
1660:showed that if any problem in
1465:pseudorandom number generators
680:, we get the complexity class
485:is any positive constant, and
436:
424:
368:
356:
233:if and only if there exists a
13:
1:
2042:
1929:10.1016/S0019-9958(86)80012-2
1792:
614:. However, in the 2002 paper
220:
2144:10.1016/0890-5401(87)90057-5
1960:10.1007/978-3-642-22670-0_20
1949:. In Goldreich, Oded (ed.).
457:is less than or equal to 1/3
281:Unlike the complexity class
235:probabilistic Turing machine
202:Informally, a problem is in
50:probabilistic Turing machine
7:
2131:Information and Computation
2125:; Verbeek, Rutger (1987b).
1847:Pulling Out The Quantumness
1759:
862:for itself, meaning that a
658:polynomial identity testing
652:) still not known to be in
501:
27:Concept in computer science
10:
2614:
2579:List of complexity classes
1952:Wigderson, David Zuckerman
1787:List of complexity classes
1162:. Moreover, relative to a
1077:in this case. Thus either
610:whether a given number is
400:, the fraction of strings
332:, the fraction of strings
2576:
2535:
2499:
2443:
2336:
2216:
2115:10.1007/3-540-18170-9_166
1981:has publishable proofs".
1882:SIAM Journal on Computing
1178:is strictly contained in
888:The relationship between
191:
139:
91:
2568:Interactive proof system
2057:Computational Complexity
1983:Computational Complexity
1942:Goldreich, Oded (2011).
995:Sipser–Lautemann theorem
494:as a consequence of the
448:{\displaystyle M(x,y)=1}
380:{\displaystyle M(x,y)=1}
74:probabilistic algorithms
2045:Simon Fraser University
1916:Information and Control
602:but not known to be in
583:but not known to be in
492:drops off exponentially
2522:Arithmetical hierarchy
2053:Christos Papadimitriou
1739:
1601:
1472:computation, that is,
1319:
1243:
1047:
993:. More precisely, the
977:is a strict subset of
870:problems instantly (a
835:
800:
575:are obviously also in
555:
449:
381:
92:BPP algorithm (1 run)
64:is one of the largest
2517:Grzegorczyk hierarchy
2512:Exponential hierarchy
2444:Considered infeasible
2033:10.1145/258533.258590
1944:"In a World of P=BPP"
1740:
1602:
1320:
1244:
1166:with probability 1,
1048:
806:
774:
738:Monte Carlo algorithm
556:
450:
382:
2507:Polynomial hierarchy
2337:Suspected infeasible
1849:, December 20, 2005
1822:. February 26, 2003.
1805:Valentine Kabanets,
1673:
1632:polynomial hierarchy
1620:sub-exponential time
1533:
1339:is instance length;
1257:
1195:
1001:
987:polynomial hierarchy
791:), which generalise
742:randomized algorithm
723:is known to contain
518:
418:
350:
2536:Families of classes
2217:Considered feasible
1878:Bennett, Charles H.
1654:Russell Impagliazzo
1510:showed that unless
1452:ZPP=BPP=EXP<NEXP
1375: —
750:Las Vegas algorithm
692:, we get the class
606:was the problem of
2210:Complexity classes
2172:2003-08-05 at the
2086:. PWS Publishing.
1995:10.1007/bf01275486
1809:, October 28, 2003
1735:
1597:
1449:oracle (and hence
1393:
1373:
1315:
1239:
1134:Closure properties
1043:
836:
801:
551:
445:
377:
192:for some constant
44:) is the class of
2585:
2584:
2527:Boolean hierarchy
2500:Class hierarchies
1866:. pp. 75–83.
1566:
1540:
1526:is contained in
1391:
1371:
1097:Adleman's theorem
953:It is known that
838:It is known that
758:. Alternatively,
627:and his students
536:
412:|) which satisfy
344:|) which satisfy
200:
199:
46:decision problems
16:(Redirected from
2605:
2203:
2196:
2189:
2180:
2179:
2148:
2146:
2123:Karpinski, Marek
2118:
2103:Karpinski, Marek
2097:
2085:
2070:
2048:
2035:
2013:
2007:
2006:
1970:
1964:
1963:
1948:
1939:
1933:
1932:
1931:
1911:
1905:
1904:
1874:
1868:
1867:
1856:
1850:
1843:
1837:
1836:
1829:
1823:
1816:
1810:
1803:
1744:
1742:
1741:
1736:
1731:
1727:
1726:
1704:
1703:
1682:
1681:
1606:
1604:
1603:
1598:
1593:
1589:
1588:
1587:
1586:
1568:
1567:
1561:
1560:
1542:
1541:
1454:
1453:
1448:
1447:
1439:
1438:
1434:
1430:
1425:
1424:
1420:
1415:
1414:
1409:
1408:
1382:
1381:
1376:
1326:
1324:
1322:
1321:
1316:
1314:
1313:
1250:
1248:
1246:
1245:
1240:
1238:
1237:
1236:
1227:
1226:
1210:
1209:
1111:is contained in
1105:Boolean circuits
1052:
1050:
1049:
1044:
1042:
1041:
1029:
1028:
1016:
1015:
924:is contained in
842:is closed under
690:quantum computer
625:Manindra Agrawal
571:All problems in
562:
560:
558:
557:
552:
550:
549:
537:
529:
527:
526:
509:
456:
454:
452:
451:
446:
388:
386:
384:
383:
378:
89:
88:
32:
21:
2613:
2612:
2608:
2607:
2606:
2604:
2603:
2602:
2588:
2587:
2586:
2581:
2572:
2531:
2495:
2439:
2433:PSPACE-complete
2332:
2212:
2207:
2174:Wayback Machine
2158:
2094:
2067:
2039:
2038:
2027:, pp. 220–229.
2014:
2010:
1971:
1967:
1946:
1940:
1936:
1912:
1908:
1894:10.1137/0210008
1875:
1871:
1857:
1853:
1845:Lance Fortnow,
1844:
1840:
1831:
1830:
1826:
1817:
1813:
1804:
1800:
1795:
1762:
1713:
1709:
1705:
1687:
1686:
1677:
1676:
1674:
1671:
1670:
1642:, collapses to
1582:
1578:
1577:
1573:
1569:
1563:
1562:
1550:
1546:
1537:
1536:
1534:
1531:
1530:
1461:
1459:Derandomization
1451:
1450:
1442:
1441:
1440:. Also, for a
1436:
1432:
1428:
1427:
1422:
1418:
1417:
1412:
1411:
1406:
1405:
1398:
1389:
1379:
1378:
1374:
1261:
1260:
1258:
1255:
1254:
1252:
1229:
1228:
1216:
1215:
1214:
1199:
1198:
1196:
1193:
1192:
1190:
1144:
1136:
1053:. As a result,
1037:
1033:
1024:
1020:
1005:
1004:
1002:
999:
998:
967:is a subset of
959:is a subset of
932:problems, then
920:or neither. If
916:is a subset of
769:
722:
715:
674:
672:Related classes
569:
568:
563:
539:
538:
528:
522:
521:
519:
516:
515:
513:
511:
504:
419:
416:
415:
413:
351:
348:
347:
345:
294:Alternatively,
223:
159:
157:
154:
152:
140:BPP algorithm (
107:
105:
102:
101:
72:have efficient
54:polynomial time
28:
23:
22:
15:
12:
11:
5:
2611:
2601:
2600:
2583:
2582:
2577:
2574:
2573:
2571:
2570:
2565:
2560:
2555:
2550:
2545:
2539:
2537:
2533:
2532:
2530:
2529:
2524:
2519:
2514:
2509:
2503:
2501:
2497:
2496:
2494:
2493:
2488:
2483:
2478:
2473:
2468:
2463:
2458:
2453:
2447:
2445:
2441:
2440:
2438:
2437:
2436:
2435:
2425:
2420:
2419:
2418:
2408:
2403:
2398:
2393:
2388:
2383:
2378:
2373:
2372:
2371:
2369:co-NP-complete
2366:
2361:
2356:
2346:
2340:
2338:
2334:
2333:
2331:
2330:
2325:
2320:
2315:
2310:
2305:
2300:
2299:
2298:
2288:
2283:
2278:
2273:
2272:
2271:
2261:
2256:
2251:
2246:
2241:
2236:
2231:
2226:
2220:
2218:
2214:
2213:
2206:
2205:
2198:
2191:
2183:
2177:
2176:
2164:
2157:
2156:External links
2154:
2153:
2152:
2149:
2137:(2): 178–189.
2119:
2099:
2092:
2076:Michael Sipser
2072:
2065:
2049:
2037:
2036:
2008:
1989:(4): 307–318.
1965:
1934:
1922:(3): 231–243,
1906:
1869:
1860:Adleman, L. M.
1851:
1838:
1824:
1811:
1797:
1796:
1794:
1791:
1790:
1789:
1784:
1777:
1770:
1761:
1758:
1746:
1745:
1734:
1730:
1725:
1722:
1719:
1716:
1712:
1708:
1702:
1699:
1696:
1693:
1690:
1685:
1680:
1608:
1607:
1596:
1592:
1585:
1581:
1576:
1572:
1559:
1556:
1553:
1549:
1545:
1460:
1457:
1390:
1369:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1235:
1232:
1225:
1222:
1219:
1213:
1208:
1205:
1202:
1143:
1142:Relativization
1140:
1135:
1132:
1107:, which means
1040:
1036:
1032:
1027:
1023:
1019:
1014:
1011:
1008:
875:oracle machine
768:
765:
720:
713:
686:Turing machine
673:
670:
564:
548:
545:
542:
535:
532:
525:
512:
506:
503:
500:
496:Chernoff bound
459:
458:
444:
441:
438:
435:
432:
429:
426:
423:
390:
376:
373:
370:
367:
364:
361:
358:
355:
322:
287:, the machine
279:
278:
263:
248:
222:
219:
218:
217:
214:
211:
198:
197:
189:
188:
185:
182:
178:
177:
174:
171:
167:
166:
163:
160:
155:
150:
149:
146:
145:
137:
136:
133:
130:
126:
125:
122:
119:
115:
114:
111:
108:
103:
99:
97:
94:
93:
80:also contains
56:with an error
48:solvable by a
26:
9:
6:
4:
3:
2:
2610:
2599:
2596:
2595:
2593:
2580:
2575:
2569:
2566:
2564:
2561:
2559:
2556:
2554:
2551:
2549:
2546:
2544:
2541:
2540:
2538:
2534:
2528:
2525:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2504:
2502:
2498:
2492:
2489:
2487:
2484:
2482:
2479:
2477:
2474:
2472:
2469:
2467:
2464:
2462:
2459:
2457:
2454:
2452:
2449:
2448:
2446:
2442:
2434:
2431:
2430:
2429:
2426:
2424:
2421:
2417:
2414:
2413:
2412:
2409:
2407:
2404:
2402:
2399:
2397:
2394:
2392:
2389:
2387:
2384:
2382:
2379:
2377:
2374:
2370:
2367:
2365:
2362:
2360:
2357:
2355:
2352:
2351:
2350:
2347:
2345:
2342:
2341:
2339:
2335:
2329:
2326:
2324:
2321:
2319:
2316:
2314:
2311:
2309:
2306:
2304:
2301:
2297:
2294:
2293:
2292:
2289:
2287:
2284:
2282:
2279:
2277:
2274:
2270:
2267:
2266:
2265:
2262:
2260:
2257:
2255:
2252:
2250:
2247:
2245:
2242:
2240:
2237:
2235:
2232:
2230:
2227:
2225:
2222:
2221:
2219:
2215:
2211:
2204:
2199:
2197:
2192:
2190:
2185:
2184:
2181:
2175:
2171:
2168:
2165:
2163:
2160:
2159:
2150:
2145:
2140:
2136:
2132:
2128:
2124:
2120:
2116:
2112:
2108:
2104:
2100:
2095:
2093:0-534-94728-X
2089:
2084:
2083:
2077:
2073:
2068:
2066:0-201-53082-1
2062:
2058:
2054:
2050:
2046:
2041:
2040:
2034:
2030:
2026:
2022:
2019: =
2018:
2012:
2004:
2000:
1996:
1992:
1988:
1984:
1980:
1976:
1969:
1961:
1957:
1953:
1945:
1938:
1930:
1925:
1921:
1917:
1910:
1903:
1899:
1895:
1891:
1888:(1): 96–113,
1887:
1883:
1879:
1873:
1865:
1861:
1855:
1848:
1842:
1834:
1828:
1821:
1815:
1808:
1802:
1798:
1788:
1785:
1783:
1782:
1778:
1776:
1775:
1771:
1769:
1768:
1764:
1763:
1757:
1755:
1751:
1732:
1728:
1720:
1714:
1710:
1706:
1683:
1669:
1668:
1667:
1665:
1664:
1659:
1658:Avi Wigderson
1655:
1651:
1650:to collapse.
1649:
1645:
1641:
1637:
1633:
1629:
1625:
1621:
1617:
1613:
1594:
1590:
1583:
1579:
1574:
1570:
1557:
1554:
1551:
1543:
1529:
1528:
1527:
1525:
1521:
1520:
1516:collapses to
1515:
1514:
1509:
1508:Avi Wigderson
1505:
1501:
1500:Lance Fortnow
1497:
1493:
1491:
1487:
1483:
1479:
1475:
1470:
1466:
1456:
1445:
1403:
1397:
1388:
1386:
1368:
1366:
1362:
1358:
1354:
1350:
1346:
1342:
1338:
1334:
1330:
1211:
1187:
1185:
1181:
1177:
1173:
1169:
1165:
1164:random oracle
1161:
1157:
1153:
1149:
1139:
1131:
1129:
1125:
1120:
1116:
1115:
1110:
1106:
1102:
1098:
1094:
1092:
1088:
1084:
1080:
1076:
1073:collapses to
1072:
1068:
1064:
1060:
1056:
1038:
1030:
1025:
1017:
996:
992:
988:
984:
980:
976:
972:
971:
966:
962:
958:
957:
951:
949:
945:
944:
939:
935:
931:
927:
923:
919:
915:
911:
910:
905:
901:
897:
896:
891:
886:
884:
880:
876:
873:
869:
865:
861:
857:
853:
849:
845:
841:
834:
830:
826:
822:
818:
814:
810:
805:
798:
794:
790:
786:
782:
778:
773:
764:
761:
757:
756:
751:
747:
743:
739:
734:
732:
731:
726:
719:
712:
708:
704:
703:postselection
699:
697:
696:
691:
687:
683:
679:
669:
667:
663:
659:
655:
651:
650:
645:
640:
638:
634:
630:
626:
622:
621:
620:
617:PRIMES is in
613:
609:
605:
601:
596:
594:
590:
586:
582:
578:
574:
567:
533:
530:
499:
497:
493:
488:
484:
480:
476:
472:
467:
464:
442:
439:
433:
430:
427:
421:
411:
407:
403:
399:
395:
391:
374:
371:
365:
362:
359:
353:
343:
339:
335:
331:
327:
323:
320:
317:
316:
315:
313:
309:
305:
301:
297:
292:
290:
286:
285:
276:
272:
268:
264:
261:
257:
253:
249:
246:
243:
242:
241:
239:
236:
232:
228:
215:
212:
209:
208:
207:
205:
195:
190:
186:
183:
180:
179:
175:
172:
169:
168:
164:
161:
148:
147:
143:
138:
134:
131:
128:
127:
123:
120:
117:
116:
112:
109:
96:
95:
90:
87:
85:
84:
79:
75:
71:
67:
63:
59:
55:
51:
47:
43:
39:
35:
19:
2312:
2134:
2130:
2106:
2081:
2056:
2024:
2020:
2016:
2011:
1986:
1982:
1978:
1974:
1968:
1950:
1937:
1919:
1915:
1909:
1885:
1881:
1872:
1863:
1854:
1841:
1827:
1814:
1801:
1779:
1772:
1765:
1753:
1749:
1747:
1661:
1652:
1647:
1643:
1639:
1635:
1627:
1623:
1615:
1611:
1609:
1523:
1517:
1511:
1496:László Babai
1494:
1489:
1485:
1481:
1477:
1473:
1462:
1401:
1399:
1394:
1384:
1370:
1364:
1360:
1356:
1352:
1348:
1344:
1340:
1336:
1332:
1188:
1183:
1179:
1175:
1171:
1167:
1159:
1155:
1151:
1147:
1145:
1137:
1118:
1112:
1108:
1100:
1095:
1090:
1086:
1082:
1078:
1074:
1070:
1066:
1062:
1058:
1054:
997:states that
990:
982:
978:
974:
968:
964:
960:
954:
952:
947:
941:
937:
933:
925:
921:
917:
913:
907:
899:
893:
889:
887:
882:
878:
871:
867:
863:
855:
851:
847:
839:
837:
820:
759:
753:
745:
735:
728:
724:
717:
710:
706:
700:
693:
681:
677:
675:
665:
661:
653:
647:
646:(in fact in
643:
641:
636:
633:Nitin Saxena
629:Neeraj Kayal
618:
615:
603:
599:
597:
592:
588:
584:
580:
576:
572:
570:
486:
482:
478:
474:
468:
462:
460:
409:
405:
401:
397:
393:
341:
337:
333:
329:
325:
318:
314:, such that
311:
307:
303:
299:
295:
293:
288:
282:
280:
274:
270:
266:
259:
255:
251:
244:
240:, such that
237:
230:
226:
224:
203:
201:
193:
141:
81:
77:
69:
65:
61:
41:
37:
29:
2416:#P-complete
2354:NP-complete
2269:NL-complete
1612:i.o.-SUBEXP
1539:i.o.-SUBEXP
1469:conjectured
1251:(and hence
1126:, see also
930:NP-complete
846:; that is,
608:determining
225:A language
187:> 1 − 2
173:> 1 − 2
58:probability
2471:ELEMENTARY
2296:P-complete
1793:References
1610:The class
1565:i.o.-DTIME
1504:Noam Nisan
844:complement
404:of length
336:of length
221:Definition
2466:2-EXPTIME
1902:1095-7111
1666:, where
1584:ε
1552:ε
1548:⋂
1093:or both.
1061:leads to
1035:Π
1031:∩
1022:Σ
1018:⊆
783:, co-RP,
66:practical
2592:Category
2461:EXPSPACE
2456:NEXPTIME
2224:DLOGTIME
2170:Archived
2078:(1997).
2055:(1993).
2003:14802332
1760:See also
502:Problems
471:constant
392:For all
324:For all
265:For all
250:For all
153:produced
100:produced
2451:EXPTIME
2359:NP-hard
1979:EXPTIME
1513:EXPTIME
1325:
1253:
1249:
1191:
795:within
730:PostBQP
701:Adding
688:with a
561:
514:
455:
414:
396:not in
387:
346:
269:not in
196:> 0
184:< 2
176:< 2
156:Correct
104:Correct
2558:NSPACE
2553:DSPACE
2428:PSPACE
2090:
2063:
2001:
1900:
1616:SUBEXP
1506:, and
1114:P/poly
1069:since
979:PSPACE
963:, and
904:subset
852:co-BPP
833:PSPACE
831:, and
825:P/poly
797:PSPACE
302:is in
229:is in
158:answer
151:Answer
144:runs)
135:≥ 2/3
132:≤ 1/3
124:≤ 1/3
121:≥ 2/3
106:answer
98:Answer
2548:NTIME
2543:DTIME
2364:co-NP
1999:S2CID
1947:(PDF)
1392:Proof
1372:Lemma
1184:co-NP
902:is a
817:co-NP
740:is a
649:co-RP
612:prime
2376:TFNP
2088:ISBN
2061:ISBN
1898:ISSN
1656:and
1634:and
1555:>
1446:=EXP
1426:and
1367:+1.
1275:<
1266:<
1182:and
1174:and
1154:and
940:and
892:and
721:path
714:path
631:and
170:Yes
162:Yes
118:Yes
110:Yes
2491:ALL
2391:QMA
2381:FNP
2323:APX
2318:BQP
2313:BPP
2303:ZPP
2234:ACC
2139:doi
2111:doi
2029:doi
2021:BPP
1991:doi
1975:BPP
1956:doi
1924:doi
1890:doi
1781:BQP
1774:ZPP
1754:BPP
1648:not
1638:as
1628:BPP
1524:BPP
1490:BPP
1482:BPP
1467:is
1444:ZPP
1437:BPP
1433:EXP
1429:EXP
1359:+1)
1176:BPP
1172:BPP
1160:BPP
1152:BPP
1119:BPP
1109:BPP
1101:BPP
1085:or
1083:BPP
1067:BPP
983:BPP
965:BPP
961:BPP
948:BPP
926:BPP
918:BPP
906:of
900:BPP
890:BPP
883:BPP
879:BPP
872:BPP
868:BPP
864:BPP
860:low
858:is
856:BPP
848:BPP
840:BPP
821:BPP
785:BQP
777:ZPP
760:ZPP
755:ZPP
746:BPP
718:BPP
711:BPP
707:BPP
705:to
695:BQP
678:BPP
656:is
644:BPP
600:BPP
593:BPP
581:BPP
577:BPP
475:BPP
328:in
304:BPP
296:BPP
284:ZPP
254:in
231:BPP
204:BPP
181:No
165:No
129:No
113:No
78:BPP
70:BPP
62:BPP
52:in
42:BPP
2594::
2486:RE
2476:PR
2423:IP
2411:#P
2406:PP
2401:⊕P
2396:PH
2386:AM
2349:NP
2344:UP
2328:FP
2308:RP
2286:CC
2281:SC
2276:NC
2264:NL
2259:FL
2254:RL
2249:SL
2239:TC
2229:AC
2135:75
2133:.
2129:.
1997:.
1985:.
1920:71
1918:,
1896:,
1886:10
1884:,
1767:RP
1756:.
1752:=
1626:=
1522:,
1519:MA
1502:,
1498:,
1488:=
1480:=
1478:RP
1476:=
1353:kn
1333:kn
1186:.
1180:NP
1170:=
1158:≠
1150:=
1130:.
1091:NP
1089:≠
1081:=
1071:PH
1065:=
1059:NP
1057:=
991:PH
981:.
970:PP
956:RP
950:.
946:⊆
943:PH
938:RP
936:=
934:NP
922:NP
914:NP
912:,
909:NP
895:NP
885:.
881:=
854:.
850:=
829:PH
827:,
823:,
819:,
815:,
813:NP
811:,
789:PP
787:,
781:RP
779:,
736:A
733:.
725:NP
716:.
698:.
639:.
623:,
595:.
591:=
498:.
408:(|
340:(|
273:,
258:,
31:In
2481:R
2291:P
2244:L
2202:e
2195:t
2188:v
2147:.
2141::
2117:.
2113::
2096:.
2069:.
2047:.
2031::
2017:P
2005:.
1993::
1987:3
1962:.
1958::
1926::
1892::
1835:.
1750:P
1733:,
1729:)
1724:)
1721:n
1718:(
1715:O
1711:2
1707:(
1701:E
1698:M
1695:I
1692:T
1689:D
1684:=
1679:E
1663:E
1644:E
1640:E
1636:E
1624:P
1595:.
1591:)
1580:n
1575:2
1571:(
1558:0
1544:=
1486:P
1474:P
1435:=
1431:=
1423:P
1421:≤
1419:P
1413:E
1407:E
1402:k
1385:n
1380:E
1365:n
1361:n
1357:k
1349:n
1345:n
1341:k
1337:n
1335:(
1329:E
1311:P
1308:X
1305:E
1302:N
1299:=
1296:P
1293:X
1290:E
1287:=
1284:P
1281:P
1278:B
1272:P
1269:N
1263:P
1234:P
1231:N
1224:P
1221:X
1218:E
1212:=
1207:P
1204:P
1201:B
1168:P
1156:P
1148:P
1087:P
1079:P
1075:P
1063:P
1055:P
1039:2
1026:2
1013:P
1010:P
1007:B
975:P
809:P
793:P
682:P
666:d
662:d
654:P
637:P
619:P
604:P
589:P
585:P
573:P
547:P
544:P
541:B
534:?
531:=
524:P
510::
487:n
483:c
479:n
463:y
443:1
440:=
437:)
434:y
431:,
428:x
425:(
422:M
410:x
406:p
402:y
398:L
394:x
375:1
372:=
369:)
366:y
363:,
360:x
357:(
354:M
342:x
338:p
334:y
330:L
326:x
319:M
312:M
308:p
300:L
289:M
275:M
271:L
267:x
260:M
256:L
252:x
245:M
238:M
227:L
194:c
142:k
83:P
40:(
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.