896:
456:
448:
1070:, in a 1910 paper, analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that ran in (moderately) exponential time.
939:
Polynomial-time algorithms are closed under composition. Intuitively, this says that if one writes a function that is polynomial-time assuming that function calls are constant-time, and if those called functions themselves require polynomial time, then the entire algorithm takes polynomial time. One
1061:
also invented the notion independently and around the same time (Rabin's paper was in a 1967 proceedings of a 1966 conference, while Cobham's was in a 1965 proceedings of a 1964 conference and
Edmonds's was published in a journal in 1965, though Rabin makes no mention of either and was apparently
828:
506:. Equivalently, it is the class of decision problems where each "yes" instance has a polynomial size certificate, and certificates can be checked by a polynomial time deterministic Turing machine. The class of problems for which this is true for the "no" instances is called
864:
is given that depends only on the length of the input. Unlike for NP, however, the polynomial-time machine doesn't need to detect fraudulent advice strings; it is not a verifier. P/poly is a large class containing nearly all practical problems, including all of
717:
702:
time, because this is the total number of possible configurations; thus, L is a subset of P. Another important problem is whether L = P. We do know that P = AL, the set of problems solvable in logarithmic memory by
841:
P is strictly contained in EXPTIME. Consequently, all EXPTIME-hard problems lie outside P, and at least one of the containments to the right of P above is strict (in fact, it is widely believed that all three are
1037:
instance in polynomial time automatically gives a polynomial algorithm for the corresponding decision problem). In that case P is not a subset of NP, but P∩DEC is, where DEC is the class of decision problems.
586:
545:
196:
1519:
Mathematics of computation, 1943–1993: a half-century of computational mathematics: Mathematics of
Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia
700:
228:
948:, that can be simulated in polynomial time can simply be composed with the main polynomial-time algorithm to reduce it to a polynomial-time algorithm on a more basic machine.
999:
that there is a polynomial-time algorithm for determining if a given graph can be embedded on a torus, despite the fact that no concrete algorithm is known for this problem.
384:
322:
636:
255:
1495:(1910–1912). "The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity".
1023:
operator added to it, on ordered structures. In
Immerman's 1999 textbook on descriptive complexity, Immerman ascribes this result to Vardi and to Immerman.
1033:
P can also be defined as an algorithmic complexity class for problems that are not decision problems (even though, for example, finding the solution to a
885:
823:{\displaystyle {\mathsf {L}}\subseteq {\mathsf {AL}}={\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {PSPACE}}\subseteq {\mathsf {EXPTIME}}.}
75:". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful
991:
that characterizes (for example) the set of graphs that can be embedded on a torus; moreover, Robertson and
Seymour showed that there is an O(
1721:
1170:
944:
for itself. This is also one of the main reasons that P is considered to be a machine-independent class; any machine "feature", such as
860:, or Nonuniform Polynomial-Time. If a problem is in P/poly, then it can be solved in deterministic polynomial time provided that an
1200:
983:
Some problems are known to be solvable in polynomial time, but no concrete algorithm is known for solving them. For example, the
866:
837:
is the class of problems solvable in exponential time. Of all the classes shown above, only two strict containments are known:
1660:
1638:
1526:
1410:
1385:
1344:
1268:
1118:
600:
554:
513:
1238:
2083:
1619:
1146:
510:. P is trivially a subset of NP and of co-NP; most experts believe it is a proper subset, although this belief (the
1714:
711:, the class of problems decidable in polynomial space. Again, whether P = PSPACE is an open problem. To summarize:
499:
154:
20:
1062:
unaware of them). Cobham invented the class as a robust way of characterizing efficient algorithms, leading to
148:
984:
873:
collapses to the second level. On the other hand, it also contains some impractical problems, including some
641:
1027:
50:
2118:
1707:
1570:
1444:
1050:
390:
2099:
1906:
1610:
704:
205:
551:. Another open problem is whether NP = co-NP; since P = co-P, a negative answer would imply
1626:
1067:
952:
1087:
2088:
337:
275:
972:
2042:
1258:
1108:
1008:
606:
2037:
2032:
1352:
1162:
996:
2027:
1597:
1134:
870:
233:
8:
874:
861:
548:
995:) algorithm for determining whether a graph has a given graph as a minor. This yields a
71:
holds that P is the class of computational problems that are "efficiently solvable" or "
1063:
956:
402:
68:
2047:
1656:
1634:
1615:
1522:
1492:
1406:
1381:
1340:
1264:
1234:
1142:
1114:
1057:
are "generally credited with the invention of the notion of polynomial time," though
1020:
1016:
72:
2011:
1901:
1833:
1823:
1730:
1694:
1601:
1593:
1582:
1558:
1474:
1426:
1373:
1312:
1309:
STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing
1289:
1286:
STOC '82: Proceedings of the fourteenth annual ACM symposium on Theory of computing
1209:
1058:
1034:
941:
908:
900:
495:
472:
414:
406:
58:
46:
42:
1587:
Mathematical
Aspects of Computer Science. Proc. 1966 Sympos. Appl. Math., Vol. XIX
895:
2006:
1996:
1953:
1943:
1936:
1926:
1916:
1874:
1869:
1864:
1848:
1828:
1806:
1801:
1796:
1784:
1779:
1774:
1769:
1514:
988:
916:
904:
889:
503:
491:
480:
464:
425:
418:
140:
88:
62:
455:
401:
P is known to contain many natural problems, including the decision versions of
2001:
1889:
1764:
1689:
1683:
1678:
1648:
1605:
964:
592:
2112:
1431:
Mathematical
Aspects of Computer Science. Proc. Sympos. Appl. Math., Vol. XIX
1254:
1104:
960:
945:
76:
447:
1562:
1546:
1478:
1462:
1365:
1307:
Immerman, Neil (1982). "Relational
Queries Computable in Polynomial Time".
1214:
1195:
1054:
1046:
968:
432:
410:
1377:
1316:
1293:
1879:
1789:
1284:
Vardi, Moshe Y. (1982). "The
Complexity of Relational Query Languages".
1991:
1816:
1228:
1191:
881:
850:
436:
409:. In 2002, it was shown that the problem of determining if a number is
54:
978:
1986:
1699:
596:
1981:
1976:
1921:
1744:
1521:. Providence, RI: American Mathematical Society. pp. 503–504.
94:
is in P if and only if there exists a deterministic Turing machine
1971:
1449:
Logic, Methodology and Philos. Sci. (Proc. 1964 Internat. Congr.)
1196:"Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis"
1012:
834:
2078:
2073:
1948:
1931:
1573:(1965). "The intrinsic computational difficulty of functions".
1447:(1965). "The intrinsic computational difficulty of functions".
920:
857:
708:
484:
476:
1026:
It was published in 2001 that PTIME corresponds to (positive)
2068:
2063:
1884:
1229:
Hopcroft, John E.; Rajeev
Motwani; Jeffrey D. Ullman (2001).
507:
468:
33:
1339:. Springer Science & Business Media. pp. 5 and 37.
1896:
1754:
1575:
Proc. Logic, Methodology, and
Philosophy of Science II 1964
1231:
Introduction to automata theory, languages, and computation
1353:
http://mjn.host.cs.st-andrews.ac.uk/publications/2001d.pdf
1911:
1843:
1838:
1759:
1749:
1233:(2. ed.). Boston: Addison-Wesley. pp. 425–426.
928:
912:
451:
A representation of the relation among complexity classes
1622:. Section 34.1: Polynomial time, pp. 971–979.
923:. It is unknown if any of these containments are strict.
424:
Several natural problems are complete for P, including
1653:
Introduction to the Theory of Computation, 2nd Edition
877:
such as the unary version of any undecidable problem.
581:{\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}
540:{\displaystyle {\mathsf {P}}\subsetneq {\mathsf {NP}}}
720:
644:
609:
557:
516:
389:
The circuit definition can be weakened to use only a
340:
278:
236:
208:
157:
1133:
1097:
1011:, P can be described as the problems expressible in
1614:, Second Edition. MIT Press and McGraw–Hill, 2001.
979:
Pure existence proofs of polynomial-time algorithms
931:, it is unknown whether the containment is strict.
899:
P in relation to probabilistic complexity classes (
1667:Section 7.2: The Class P, pp. 256–263;.
822:
694:
630:
580:
539:
378:
316:
249:
222:
190:
442:
2110:
1491:
1002:
1334:
1086:Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "
951:Languages in P are also closed under reversal,
393:family without changing the complexity class.
1715:
1625:
1328:
16:Class of problems solvable in polynomial time
1190:
185:
158:
139:P can also be viewed as a uniform family of
1585:(1967). "Mathematical theory of automata".
1429:(1967). "Mathematical theory of automata".
1358:
591:P is also known to be at least as large as
459:Inclusions of complexity classes including
191:{\displaystyle \{C_{n}:n\in \mathbb {N} \}}
1722:
1708:
987:guarantees that there is a finite list of
1263:. New York: Springer-Verlag. p. 66.
1213:
216:
181:
1513:
1306:
1253:
1103:
894:
454:
446:
435:) on alternating graphs. The article on
396:
1545:
1461:
1364:
1201:Journal of Computer and System Sciences
707:. P is also known to be no larger than
595:, the class of problems decidable in a
2111:
1729:
1647:
1569:
1443:
884:and D. Sivakumar, building on work by
812:
809:
806:
803:
800:
797:
794:
784:
781:
778:
775:
772:
769:
759:
756:
746:
736:
733:
723:
695:{\displaystyle 2^{O(\log n)}=n^{O(1)}}
573:
570:
560:
532:
529:
519:
439:lists further relevant problems in P.
147:is in P if and only if there exists a
105:runs for polynomial time on all inputs
1703:
1581:
1549:(1965). "Paths, trees, and flowers".
1465:(1965). "Paths, trees, and flowers".
1425:
1400:
1283:
1163:"complexity theory - Why is co-P = P"
849:The most difficult problems in P are
1589:. Amer. Math. Soc. pp. 153–175.
1433:. Amer. Math. Soc. pp. 153–175.
1337:Parsing Beyond Context-Free Grammars
1173:from the original on 14 October 2020
13:
1633:. Reading, Mass.: Addison–Wesley.
1141:. Pearson Education. p. 458.
845:L is strictly contained in PSPACE.
14:
2130:
2084:Probabilistically checkable proof
1671:
940:consequence of this is that P is
223:{\displaystyle n\in \mathbb {N} }
892:that is P-complete, then L = P.
888:, showed that if there exists a
500:non-deterministic Turing machine
1507:
1485:
1455:
1437:
1419:
1394:
1372:. Springer-Verlag. p. 35.
1094:160 (2004), no. 2, pp. 781–793.
856:Another generalization of P is
261:bits as input and outputs 1 bit
21:computational complexity theory
1300:
1277:
1247:
1222:
1194:; Sivakumar, D. (April 1999).
1184:
1155:
1127:
1080:
869:. If it contains NP, then the
687:
681:
665:
653:
625:
613:
443:Relationships to other classes
413:is in P. The related class of
367:
361:
355:
347:
305:
299:
293:
285:
1:
1539:
1113:. New York: Springer-Verlag.
1003:Alternative characterizations
934:
82:
1028:range concatenation grammars
379:{\displaystyle C_{|x|}(x)=0}
317:{\displaystyle C_{|x|}(x)=1}
51:deterministic Turing machine
7:
1137:; Schaefer, Marcus (2004).
705:alternating Turing machines
638:space cannot use more than
151:family of Boolean circuits
10:
2135:
2100:List of complexity classes
1627:Papadimitriou, Christos H.
1611:Introduction to Algorithms
1041:
2097:
2056:
2020:
1964:
1857:
1737:
1655:. Course Technology Inc.
1401:Kozen, Dexter C. (2006).
985:Robertson–Seymour theorem
631:{\displaystyle O(\log n)}
490:A generalization of P is
2089:Interactive proof system
1631:Computational complexity
1335:Laura Kallmeyer (2010).
1135:Johnsonbaugh, Richard F.
1073:
494:, which is the class of
49:that can be solved by a
1405:. Springer. p. 4.
1323:Information and Control
149:polynomial-time uniform
2043:Arithmetical hierarchy
1563:10.4153/CJM-1965-045-4
1479:10.4153/CJM-1965-045-4
1260:Descriptive Complexity
1215:10.1006/jcss.1998.1615
1110:Descriptive Complexity
1009:descriptive complexity
924:
824:
696:
632:
582:
541:
487:
452:
380:
318:
251:
224:
192:
2038:Grzegorczyk hierarchy
2033:Exponential hierarchy
1965:Considered infeasible
1497:Proc. Camb. Phil. Soc
1403:Theory of Computation
1378:10.1007/3-540-27477-4
1317:10.1145/800070.802187
1294:10.1145/800070.802186
1092:Annals of Mathematics
997:nonconstructive proof
898:
825:
697:
633:
583:
542:
458:
450:
397:Notable problems in P
381:
319:
252:
250:{\displaystyle C_{n}}
225:
193:
2028:Polynomial hierarchy
1858:Suspected infeasible
1598:Charles E. Leiserson
1325:, 68 (1986), 86–104.
1311:. pp. 147–152.
1288:. pp. 137–146.
875:undecidable problems
871:polynomial hierarchy
718:
642:
607:
555:
514:
338:
276:
234:
206:
155:
41:), is a fundamental
2057:Families of classes
1738:Considered feasible
1321:Revised version in
437:P-complete problems
2119:Complexity classes
1731:Complexity classes
1493:Pocklington, H. C.
927:P is contained in
925:
820:
692:
628:
603:. A decider using
578:
537:
488:
453:
403:linear programming
376:
314:
247:
220:
188:
45:. It contains all
2106:
2105:
2048:Boolean hierarchy
2021:Class hierarchies
1662:978-0-534-95097-2
1640:978-0-201-53082-7
1583:Rabin, Michael O.
1528:978-0-8218-0291-5
1451:. pp. 24–30.
1427:Rabin, Michael O.
1412:978-1-84628-297-3
1387:978-3-540-21045-0
1370:Complexity Theory
1346:978-3-642-14846-0
1270:978-0-387-98600-5
1120:978-0-387-98600-5
1068:H. C. Pocklington
1021:least fixed point
1017:first-order logic
886:Mitsunori Ogihara
496:decision problems
415:function problems
47:decision problems
2126:
1724:
1717:
1710:
1701:
1700:
1666:
1644:
1602:Ronald L. Rivest
1594:Thomas H. Cormen
1590:
1578:
1577:. North Holland.
1566:
1551:Canadian J. Math
1533:
1532:
1515:Gautschi, Walter
1511:
1505:
1504:
1489:
1483:
1482:
1467:Canadian J. Math
1459:
1453:
1452:
1441:
1435:
1434:
1423:
1417:
1416:
1398:
1392:
1391:
1362:
1356:
1350:
1332:
1326:
1320:
1304:
1298:
1297:
1281:
1275:
1274:
1251:
1245:
1244:
1226:
1220:
1219:
1217:
1188:
1182:
1181:
1179:
1178:
1159:
1153:
1152:
1131:
1125:
1124:
1101:
1095:
1084:
1035:2-satisfiability
989:forbidden minors
829:
827:
826:
821:
816:
815:
788:
787:
763:
762:
750:
749:
740:
739:
727:
726:
701:
699:
698:
693:
691:
690:
669:
668:
637:
635:
634:
629:
587:
585:
584:
579:
577:
576:
564:
563:
549:remains unproven
546:
544:
543:
538:
536:
535:
523:
522:
407:maximum matching
405:, and finding a
391:logspace uniform
385:
383:
382:
377:
360:
359:
358:
350:
323:
321:
320:
315:
298:
297:
296:
288:
256:
254:
253:
248:
246:
245:
229:
227:
226:
221:
219:
197:
195:
194:
189:
184:
170:
169:
141:Boolean circuits
59:computation time
43:complexity class
27:, also known as
2134:
2133:
2129:
2128:
2127:
2125:
2124:
2123:
2109:
2108:
2107:
2102:
2093:
2052:
2016:
1960:
1954:PSPACE-complete
1853:
1733:
1728:
1674:
1663:
1649:Sipser, Michael
1641:
1542:
1537:
1536:
1529:
1512:
1508:
1490:
1486:
1460:
1456:
1442:
1438:
1424:
1420:
1413:
1399:
1395:
1388:
1363:
1359:
1347:
1333:
1329:
1305:
1301:
1282:
1278:
1271:
1252:
1248:
1241:
1227:
1223:
1189:
1185:
1176:
1174:
1161:
1160:
1156:
1149:
1132:
1128:
1121:
1102:
1098:
1085:
1081:
1076:
1064:Cobham's thesis
1044:
1005:
981:
973:complementation
937:
890:sparse language
793:
792:
768:
767:
755:
754:
745:
744:
732:
731:
722:
721:
719:
716:
715:
677:
673:
649:
645:
643:
640:
639:
608:
605:
604:
569:
568:
559:
558:
556:
553:
552:
528:
527:
518:
517:
515:
512:
511:
504:polynomial time
498:decidable by a
445:
399:
354:
346:
345:
341:
339:
336:
335:
292:
284:
283:
279:
277:
274:
273:
241:
237:
235:
232:
231:
215:
207:
204:
203:
180:
165:
161:
156:
153:
152:
85:
69:Cobham's thesis
63:polynomial time
17:
12:
11:
5:
2132:
2122:
2121:
2104:
2103:
2098:
2095:
2094:
2092:
2091:
2086:
2081:
2076:
2071:
2066:
2060:
2058:
2054:
2053:
2051:
2050:
2045:
2040:
2035:
2030:
2024:
2022:
2018:
2017:
2015:
2014:
2009:
2004:
1999:
1994:
1989:
1984:
1979:
1974:
1968:
1966:
1962:
1961:
1959:
1958:
1957:
1956:
1946:
1941:
1940:
1939:
1929:
1924:
1919:
1914:
1909:
1904:
1899:
1894:
1893:
1892:
1890:co-NP-complete
1887:
1882:
1877:
1867:
1861:
1859:
1855:
1854:
1852:
1851:
1846:
1841:
1836:
1831:
1826:
1821:
1820:
1819:
1809:
1804:
1799:
1794:
1793:
1792:
1782:
1777:
1772:
1767:
1762:
1757:
1752:
1747:
1741:
1739:
1735:
1734:
1727:
1726:
1719:
1712:
1704:
1698:
1697:
1690:Complexity Zoo
1686:
1679:Complexity Zoo
1673:
1672:External links
1670:
1669:
1668:
1661:
1645:
1639:
1623:
1606:Clifford Stein
1591:
1579:
1567:
1541:
1538:
1535:
1534:
1527:
1506:
1484:
1454:
1436:
1418:
1411:
1393:
1386:
1357:
1345:
1327:
1299:
1276:
1269:
1255:Immerman, Neil
1246:
1240:978-0201441246
1239:
1221:
1208:(2): 280–296.
1183:
1167:Stack Overflow
1154:
1147:
1126:
1119:
1105:Immerman, Neil
1096:
1088:PRIMES is in P
1078:
1077:
1075:
1072:
1043:
1040:
1004:
1001:
980:
977:
965:Kleene closure
936:
933:
847:
846:
843:
831:
830:
819:
814:
811:
808:
805:
802:
799:
796:
791:
786:
783:
780:
777:
774:
771:
766:
761:
758:
753:
748:
743:
738:
735:
730:
725:
689:
686:
683:
680:
676:
672:
667:
664:
661:
658:
655:
652:
648:
627:
624:
621:
618:
615:
612:
575:
572:
567:
562:
534:
531:
526:
521:
444:
441:
398:
395:
387:
386:
375:
372:
369:
366:
363:
357:
353:
349:
344:
324:
313:
310:
307:
304:
301:
295:
291:
287:
282:
262:
244:
240:
218:
214:
211:
187:
183:
179:
176:
173:
168:
164:
160:
137:
136:
121:
106:
84:
81:
15:
9:
6:
4:
3:
2:
2131:
2120:
2117:
2116:
2114:
2101:
2096:
2090:
2087:
2085:
2082:
2080:
2077:
2075:
2072:
2070:
2067:
2065:
2062:
2061:
2059:
2055:
2049:
2046:
2044:
2041:
2039:
2036:
2034:
2031:
2029:
2026:
2025:
2023:
2019:
2013:
2010:
2008:
2005:
2003:
2000:
1998:
1995:
1993:
1990:
1988:
1985:
1983:
1980:
1978:
1975:
1973:
1970:
1969:
1967:
1963:
1955:
1952:
1951:
1950:
1947:
1945:
1942:
1938:
1935:
1934:
1933:
1930:
1928:
1925:
1923:
1920:
1918:
1915:
1913:
1910:
1908:
1905:
1903:
1900:
1898:
1895:
1891:
1888:
1886:
1883:
1881:
1878:
1876:
1873:
1872:
1871:
1868:
1866:
1863:
1862:
1860:
1856:
1850:
1847:
1845:
1842:
1840:
1837:
1835:
1832:
1830:
1827:
1825:
1822:
1818:
1815:
1814:
1813:
1810:
1808:
1805:
1803:
1800:
1798:
1795:
1791:
1788:
1787:
1786:
1783:
1781:
1778:
1776:
1773:
1771:
1768:
1766:
1763:
1761:
1758:
1756:
1753:
1751:
1748:
1746:
1743:
1742:
1740:
1736:
1732:
1725:
1720:
1718:
1713:
1711:
1706:
1705:
1702:
1696:
1692:
1691:
1687:
1685:
1681:
1680:
1676:
1675:
1664:
1658:
1654:
1650:
1646:
1642:
1636:
1632:
1628:
1624:
1621:
1620:0-262-03293-7
1617:
1613:
1612:
1607:
1603:
1599:
1595:
1592:
1588:
1584:
1580:
1576:
1572:
1568:
1564:
1560:
1556:
1552:
1548:
1544:
1543:
1530:
1524:
1520:
1516:
1510:
1502:
1498:
1494:
1488:
1480:
1476:
1472:
1468:
1464:
1458:
1450:
1446:
1440:
1432:
1428:
1422:
1414:
1408:
1404:
1397:
1389:
1383:
1379:
1375:
1371:
1367:
1366:Wegener, Ingo
1361:
1355:for the proof
1354:
1348:
1342:
1338:
1331:
1324:
1318:
1314:
1310:
1303:
1295:
1291:
1287:
1280:
1272:
1266:
1262:
1261:
1256:
1250:
1242:
1236:
1232:
1225:
1216:
1211:
1207:
1203:
1202:
1197:
1193:
1187:
1172:
1168:
1164:
1158:
1150:
1148:0-02-360692-4
1144:
1140:
1136:
1130:
1122:
1116:
1112:
1111:
1106:
1100:
1093:
1089:
1083:
1079:
1071:
1069:
1065:
1060:
1056:
1052:
1048:
1039:
1036:
1031:
1029:
1024:
1022:
1018:
1014:
1010:
1000:
998:
994:
990:
986:
976:
974:
970:
966:
962:
961:concatenation
958:
954:
949:
947:
946:random access
943:
932:
930:
922:
919:), allwithin
918:
914:
910:
906:
902:
897:
893:
891:
887:
883:
878:
876:
872:
868:
863:
862:advice string
859:
854:
852:
844:
840:
839:
838:
836:
817:
789:
764:
751:
741:
728:
714:
713:
712:
710:
706:
684:
678:
674:
670:
662:
659:
656:
650:
646:
622:
619:
616:
610:
602:
598:
594:
589:
565:
550:
524:
509:
505:
502:that runs in
501:
497:
493:
486:
482:
478:
474:
470:
466:
462:
457:
449:
440:
438:
434:
430:
429:-connectivity
428:
422:
420:
416:
412:
408:
404:
394:
392:
373:
370:
364:
351:
342:
333:
329:
325:
311:
308:
302:
289:
280:
271:
267:
263:
260:
242:
238:
212:
209:
201:
200:
199:
177:
174:
171:
166:
162:
150:
146:
143:. A language
142:
134:
130:
126:
122:
119:
115:
111:
107:
104:
101:
100:
99:
97:
93:
90:
80:
78:
77:rule of thumb
74:
70:
66:
64:
60:
56:
52:
48:
44:
40:
36:
35:
30:
26:
22:
1811:
1695:Class P/poly
1688:
1677:
1652:
1630:
1609:
1586:
1574:
1571:Cobham, Alan
1554:
1550:
1518:
1509:
1500:
1496:
1487:
1470:
1466:
1457:
1448:
1445:Cobham, Alan
1439:
1430:
1421:
1402:
1396:
1369:
1360:
1336:
1330:
1322:
1308:
1302:
1285:
1279:
1259:
1249:
1230:
1224:
1205:
1199:
1186:
1175:. Retrieved
1166:
1157:
1138:
1129:
1109:
1099:
1091:
1082:
1066:. However,
1049:states that
1045:
1032:
1025:
1006:
992:
982:
969:homomorphism
953:intersection
950:
938:
926:
879:
855:
848:
832:
601:memory space
590:
547:hypothesis)
489:
460:
433:reachability
426:
423:
400:
388:
331:
327:
269:
265:
258:
198:, such that
144:
138:
132:
128:
124:
117:
113:
109:
102:
98:, such that
95:
91:
86:
67:
38:
32:
28:
24:
18:
1937:#P-complete
1875:NP-complete
1790:NL-complete
1557:: 449–467.
1547:Edmonds, J.
1473:: 449–467.
1463:Edmonds, J.
1192:Cai, Jin-Yi
597:logarithmic
1992:ELEMENTARY
1817:P-complete
1540:References
1177:2020-10-14
1139:Algorithms
967:, inverse
935:Properties
882:Jin-Yi Cai
853:problems.
851:P-complete
599:amount of
83:Definition
57:amount of
55:polynomial
1987:2-EXPTIME
907:, co-RP,
880:In 1999,
790:⊆
765:⊆
752:⊆
729:⊆
660:
620:
566:⊊
525:⊊
213:∈
178:∈
135:outputs 0
120:outputs 1
73:tractable
2113:Category
1982:EXPSPACE
1977:NEXPTIME
1745:DLOGTIME
1651:(2006).
1629:(1994).
1517:(1994).
1368:(2005).
1257:(1999).
1171:Archived
1107:(1999).
842:strict).
326:For all
264:For all
202:For all
123:For all
108:For all
89:language
53:using a
1972:EXPTIME
1880:NP-hard
1684:Class P
1351:citing
1055:Edmonds
1042:History
1019:with a
1013:FO(LFP)
835:EXPTIME
330:not in
127:not in
2079:NSPACE
2074:DSPACE
1949:PSPACE
1659:
1637:
1618:
1604:, and
1525:
1503:: 1–5.
1409:
1384:
1343:
1267:
1237:
1145:
1117:
1051:Cobham
1015:, the
971:, and
921:PSPACE
858:P/poly
833:Here,
709:PSPACE
485:PSPACE
483:, and
477:P/poly
257:takes
2069:NTIME
2064:DTIME
1885:co-NP
1074:Notes
1059:Rabin
1047:Kozen
957:union
508:co-NP
469:co-NP
411:prime
61:, or
34:DTIME
29:PTIME
1897:TFNP
1657:ISBN
1635:ISBN
1616:ISBN
1523:ISBN
1407:ISBN
1382:ISBN
1341:ISBN
1265:ISBN
1235:ISBN
1143:ISBN
1115:ISBN
1053:and
431:(or
2012:ALL
1912:QMA
1902:FNP
1844:APX
1839:BQP
1834:BPP
1824:ZPP
1755:ACC
1559:doi
1475:doi
1374:doi
1313:doi
1290:doi
1210:doi
1090:",
1007:In
942:low
929:BQP
913:BQP
909:BPP
901:ZPP
867:BPP
657:log
617:log
473:BPP
417:is
268:in
112:in
31:or
19:In
2115::
2007:RE
1997:PR
1944:IP
1932:#P
1927:PP
1922:⊕P
1917:PH
1907:AM
1870:NP
1865:UP
1849:FP
1829:RP
1807:CC
1802:SC
1797:NC
1785:NL
1780:FL
1775:RL
1770:SL
1760:TC
1750:AC
1693::
1682::
1608:.
1600:,
1596:,
1555:17
1553:.
1501:16
1499:.
1471:17
1469:.
1380:.
1206:58
1204:.
1198:.
1169:.
1165:.
1030:.
975:.
963:,
959:,
955:,
917:PP
915:,
911:,
905:RP
903:,
588:.
492:NP
481:PH
479:,
475:,
471:,
467:,
465:NP
463:,
427:st
421:.
419:FP
334:,
272:,
230:,
131:,
116:,
87:A
79:.
65:.
23:,
2002:R
1812:P
1765:L
1723:e
1716:t
1709:v
1665:.
1643:.
1565:.
1561::
1531:.
1481:.
1477::
1415:.
1390:.
1376::
1349:.
1319:.
1315::
1296:.
1292::
1273:.
1243:.
1218:.
1212::
1180:.
1151:.
1123:.
993:n
818:.
813:E
810:M
807:I
804:T
801:P
798:X
795:E
785:E
782:C
779:A
776:P
773:S
770:P
760:P
757:N
747:P
742:=
737:L
734:A
724:L
688:)
685:1
682:(
679:O
675:n
671:=
666:)
663:n
654:(
651:O
647:2
626:)
623:n
614:(
611:O
593:L
574:P
571:N
561:P
533:P
530:N
520:P
461:P
374:0
371:=
368:)
365:x
362:(
356:|
352:x
348:|
343:C
332:L
328:x
312:1
309:=
306:)
303:x
300:(
294:|
290:x
286:|
281:C
270:L
266:x
259:n
243:n
239:C
217:N
210:n
186:}
182:N
175:n
172::
167:n
163:C
159:{
145:L
133:M
129:L
125:x
118:M
114:L
110:x
103:M
96:M
92:L
39:n
37:(
25:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
