303:
342:
3073:
239:
Given any decision problem in NP, construct a non-deterministic machine that solves it in polynomial time. Then for each input to that machine, build a
Boolean expression that computes whether when that specific input is passed to the machine, the machine runs correctly, and the machine halts and
2800:
240:
answers "yes". Then the expression can be satisfied if and only if there is a way for the machine to run correctly and answer "yes", so the satisfiability of the constructed expression is equivalent to asking whether or not the machine will answer "yes".
610:
4266:, the question of whether there is a deterministic polynomial-time algorithm for SAT (and consequently all other NP-complete problems) is still a famous unsolved problem, despite decades of intense effort by complexity theorists,
257:
There are two parts to proving that the
Boolean satisfiability problem (SAT) is NP-complete. One is to show that SAT is an NP problem. The other is to show that every NP problem can be reduced to an instance of a SAT problem by a
3281:
2198:
4827:
First modify the proof of the Cook–Levin theorem, so that the resulting formula is in conjunctive normal form, then introduce new variables to split clauses with more than 3 atoms. For example, the clause
3068:{\displaystyle {\begin{array}{l}(H_{i,k}\land Q_{q,k}\land T_{i,\sigma ,k})\to \\\bigvee _{((q,\sigma ),(q',\sigma ',d))\in \delta }(H_{i+d,\ k+1}\land Q_{q',\ k+1}\land T_{i,\ \sigma ',\ k+1})\end{array}}}
4935:
1911:
2741:
2581:
2345:
4252:(CNF) with exactly three variables or negations of variables per clause) to be NP-complete by showing how to reduce (in polynomial time) any instance of SAT to an equivalent instance of 3SAT.
2050:
426:
2471:
155:
such that, for all subexponential deterministic-time complexity classes T, the relativized complexity class NP is not a subset of T. In particular, for this oracle, P ≠ NP.
4870:
4111:
3774:
1464:
868:
4244:
Karp showed each of his problems to be NP-complete by reducing another problem (already shown to be NP-complete) to that problem. For example, he showed the problem 3SAT (the
4173:
1505:
935:
5025:
523:
2613:
2377:
2230:
1943:
3640:
894:
518:
92:
problem can be solved by a deterministic polynomial-time algorithm. The question of whether such an algorithm for
Boolean satisfiability exists is thus equivalent to the
3685:
3596:
3198:
2792:
2662:
2279:
2101:
1992:
1244:
1099:
4705:
4987:
3816:
3422:
3109:
1563:
990:
1639:
4552:
3488:
3455:
2515:
2419:
1825:
1761:
1725:
1382:
1280:
1135:
466:
173:. Additionally he found for each of these problems an algorithm that solves it in optimal time (in particular, these algorithms run in polynomial time if and only if
1665:
815:
492:
4014:
3957:
3925:
3314:
659:
4955:
4514:
4034:
3981:
3896:
3876:
3856:
3836:
3705:
3548:
3528:
3508:
3383:
3363:
3343:
3151:
3131:
1785:
1685:
1605:
1585:
1407:
1342:
1322:
1302:
1197:
1177:
1157:
1052:
1032:
1012:
786:
766:
742:
722:
699:
679:
630:
446:
363:
327:
4222:
suffices) to an instance of the
Boolean satisfiability problem. This means that if the Boolean satisfiability problem could be solved in polynomial time by a
5097:
88:
An important consequence of this theorem is that if there exists a deterministic polynomial-time algorithm for solving
Boolean satisfiability, then every
4178:
The use of SAT to prove the existence of an NP-complete problem can be extended to other computational problems in logic, and to completeness for other
162:'s paper, "Universal search problems", was published in 1973, although it was mentioned in talks and submitted for publication a few years earlier.
4779:
4957:
is a new variable that will not be used anywhere else in the expression. Clauses with fewer than three atoms can be padded; for example,
4263:
4401:
3206:
2109:
265:
SAT is in NP because any assignment of
Boolean values to Boolean variables that is claimed to satisfy the given expression can be
169:, which require finding solutions rather than simply determining existence. He provided six such NP-complete search problems, or
4875:
4399:
Dekhtiar, M. (1969). "On the impossibility of eliminating exhaustive search in computing a function relative to its graph".
2670:
128:'s subsequent paper, "Reducibility among combinatorial problems", generated renewed interest in Cook's paper by providing a
1841:
4448:
259:
133:
17:
2523:
2287:
2000:
120:
published his paper "The complexity of theorem proving procedures" in conference proceedings of the newly founded ACM
5059:
4348:
4308:
4238:
129:
3987:
the membership of the given problem in NP, the transformation cannot be effectively computed, unless an upper bound
121:
370:
31:
4245:
375:
143:
The theoretical interest in NP-completeness was also enhanced by the work of
Theodore P. Baker, John Gill, and
43:
2427:
132:. Karp also introduced the notion of completeness used in the current definition of NP-completeness (i.e., by
4607:
296:
5046:
4831:
4328:
4223:
4047:
3710:
158:
In the USSR, a result equivalent to Baker, Gill, and
Solovay's was published in 1969 by M. Dekhtiar. Later
97:
63:
4202:. Analogously, dependency quantified boolean formulas encode computation with a Turing machine limited to
1416:
820:
4565:
4183:
4116:
605:{\displaystyle \delta \subseteq ((Q\setminus F)\times \Sigma )\times (Q\times \Sigma \times \{-1,+1\})}
4194:
for its variables. The QBF problem can be used to encode computation with a Turing machine limited to
1469:
899:
5051:
4992:
4299:(1972). "Reducibility Among Combinatorial Problems". In Raymond E. Miller; James W. Thatcher (eds.).
4198:, proving that there exists a problem (the recognition of true quantified Boolean formulas) that is
112:
was developed in the late 1960s and early 1970s in parallel by researchers in North
America and the
3601:
873:
497:
4739:
4249:
3645:
3556:
3158:
2752:
2622:
2239:
2061:
1952:
1204:
1059:
4672:
4960:
4191:
3782:
3388:
3079:
1529:
956:
55:
2587:
2351:
2204:
1917:
1612:
4519:
4267:
3984:
3460:
3427:
2482:
2386:
1797:
1733:
1692:
1349:
1252:
1107:
451:
1644:
794:
471:
5069:
4187:
3990:
3933:
3901:
3776:. Thus the transformation is certainly a polynomial-time many-one reduction, as required.
3290:
635:
8:
4271:
1410:
306:
174:
93:
4237:'s landmark paper, "Reducibility among combinatorial problems", in which he showed that
4940:
4630:
4588:
4499:
4465:
4439:
4354:
4175:. The quasilinear result first appeared seven years after Cook's original publication.
4019:
3966:
3960:
3881:
3861:
3841:
3821:
3690:
3533:
3513:
3493:
3368:
3348:
3328:
3136:
3116:
1770:
1670:
1590:
1570:
1392:
1327:
1307:
1287:
1182:
1162:
1142:
1037:
1017:
997:
771:
751:
727:
707:
684:
664:
615:
431:
348:
312:
220:
212:
4813:
4796:
5073:
5055:
4758:
4723:
4668:
4344:
4304:
4219:
4218:
The proof shows that every problem in NP can be reduced in polynomial time (in fact,
165:
Levin's approach was slightly different from Cook's and Karp's in that he considered
5041:
4808:
4754:
4718:
4634:
4622:
4592:
4580:
4457:
4381:
4372:
T. P. Baker; J. Gill; R. Solovay (1975). "Relativizations of the P = NP question".
4358:
4336:
4227:
4179:
291:
are equivalent, and the proof can be found in many textbooks, for example Sipser's
216:
186:
27:
Boolean satisfiability is NP-complete and therefore that NP-complete problems exist
4469:
4259:, and new problems are still being discovered to be within that complexity class.
5065:
4233:
The significance of NP-completeness was made clear by the publication in 1972 of
4203:
4199:
201:
192:
109:
89:
59:
51:
47:
4044:
While the above method encodes a non-deterministic Turing machine in complexity
791:
The
Boolean expression uses the variables set out in the following table. Here,
4773:
4484:
745:
197:
166:
148:
144:
5091:
5077:
5037:
4797:"Lower bounds for multiplayer noncooperative games of incomplete information"
4255:
Garey and Johnson presented more than 300 NP-complete problems in their book
4461:
4420:
4324:
4296:
4234:
159:
137:
125:
117:
82:
78:
74:
70:
4626:
4584:
4340:
96:, which is still widely considered the most important unsolved problem in
81:, based on an earlier proof (using a different notion of reducibility) by
5050:. Series of Books in the Mathematical Sciences (1st ed.). New York:
4605:
4226:, then all problems in NP could be solved in polynomial time, and so the
4207:
2805:
228:
302:
4113:, the literature describes more sophisticated approaches in complexity
5047:
Computers and Intractability: A Guide to the Theory of NP-Completeness
4740:"Short propositional formulas represent nondeterministic computations"
4257:
Computers and Intractability: A Guide to the Theory of NP-Completeness
3550:
that follows the steps indicated by the assignments to the variables.
269:
in polynomial time by a deterministic Turing machine. (The statements
4424:
4385:
4333:
Proceedings of the Third Annual ACM Symposium on Theory of Computing
4186:
problem (QBF) involves Boolean formulas extended to include nested
3276:{\displaystyle \bigvee _{0\leq k\leq p(n)}\bigvee _{f\in F}Q_{f,k}}
4794:
151:
models requires exponential time. That is, there exists an oracle
341:
4195:
4516:, except for the last table row, which leads to a clause with
2193:{\displaystyle T_{i,j,k}\land T_{i,j',k+1}\rightarrow H_{i,k}}
4654:
Proceedings of the 2nd Australian Computer Science Conference
4771:
4371:
632:
accepts or rejects an instance of the problem after at most
369:
Now suppose that a given problem in NP can be solved by the
3510:
is satisfiable, then there is an accepting computation for
113:
4930:{\displaystyle (A\lor B\lor Z)\land (\lnot Z\lor C\lor D)}
3287:
Must finish in an accepting state, not later than in step
1687:, the initial symbol is the special default/blank symbol.
4496:
The number of literals in each clause does not depend on
4241:, each infamous for its intractability, are NP-complete.
3930:
The transformation makes extensive use of the polynomial
147:
who showed, in 1975, that solving NP-problems in certain
231:
to the variables that makes the entire expression true.
4239:
21 diverse combinatorial and graph theoretical problems
1413:
of the sub-expressions in the following table, for all
329:
to SAT. Data sizes and program runtimes are colored in
4606:
Nicholas Pippenger and Michael J. Fischer (Apr 1979).
3838:. The remaining lines depend only on the input length
3490:
their intended interpretations. On the other hand, if
2736:{\displaystyle \bigvee _{-p(n)\leq i\leq p(n)}H_{i,k}}
4995:
4963:
4943:
4878:
4834:
4675:
4522:
4502:
4119:
4050:
4022:
3993:
3969:
3936:
3904:
3884:
3864:
3844:
3824:
3785:
3713:
3693:
3648:
3604:
3559:
3536:
3516:
3496:
3463:
3430:
3391:
3371:
3351:
3331:
3293:
3209:
3161:
3139:
3119:
3082:
2803:
2755:
2673:
2625:
2590:
2526:
2485:
2430:
2389:
2354:
2290:
2242:
2207:
2112:
2064:
2003:
1955:
1920:
1844:
1800:
1773:
1736:
1695:
1673:
1647:
1615:
1593:
1573:
1532:
1472:
1419:
1395:
1352:
1330:
1310:
1290:
1255:
1207:
1185:
1165:
1145:
1110:
1062:
1040:
1020:
1000:
959:
902:
876:
823:
797:
774:
754:
730:
710:
687:
667:
638:
618:
526:
500:
474:
454:
434:
378:
351:
315:
4650:
A new proof of the NP completeness of satisfiability
4795:Gary Peterson; John Reif; Salman Azhar (Apr 2001).
4666:
4647:
4563:
5019:
4981:
4949:
4929:
4864:
4707:reduction from RAM computations to satisfiability"
4699:
4546:
4508:
4167:
4105:
4028:
4008:
3975:
3951:
3919:
3890:
3870:
3850:
3830:
3810:
3768:
3699:
3679:
3634:
3590:
3542:
3522:
3502:
3482:
3449:
3416:
3377:
3357:
3337:
3308:
3275:
3192:
3145:
3125:
3103:
3067:
2786:
2735:
2656:
2607:
2575:
2509:
2465:
2413:
2371:
2339:
2273:
2224:
2192:
2095:
2044:
1986:
1937:
1906:{\displaystyle \neg T_{i,j,k}\lor \neg T_{i,j',k}}
1905:
1819:
1779:
1755:
1719:
1679:
1659:
1633:
1599:
1579:
1557:
1499:
1458:
1401:
1376:
1336:
1316:
1296:
1274:
1238:
1191:
1171:
1151:
1129:
1093:
1046:
1026:
1006:
984:
929:
888:
862:
809:
780:
760:
736:
716:
693:
673:
653:
624:
604:
512:
486:
460:
440:
420:
357:
321:
4270:, and others. For more details, see the article
612:is the transition relation. Suppose further that
345:Schematized accepting computation by the machine
5089:
4262:Although many practical instances of SAT can be
2576:{\displaystyle \lnot H_{i,k}\lor \lnot H_{i',k}}
2340:{\displaystyle \lnot Q_{q,k}\lor \lnot Q_{q',k}}
2045:{\displaystyle \bigvee _{j\in \Sigma }T_{i,j,k}}
4737:
4566:"Satisfiability is quasilinear complete in NQL"
2234:Tape remains unchanged unless written by head.
4872:can be replaced by the conjunction of clauses
4329:"The complexity of theorem proving procedures"
4206:, proving that there exists a problem that is
209:instance of the Boolean satisfiability problem
4801:Computers & Mathematics with Applications
4230:NP would be equal to the complexity class P.
5036:
4780:Symposium on Foundations of Computer Science
4438:
596:
578:
250:
5098:Theorems in computational complexity theory
4442:(1984). "A survey of Russian approaches to
4402:Proceedings of the USSR Academy of Sciences
3959:. As a consequence, the above proof is not
3598:Boolean variables, each encodable in space
3878:; they formalize a generic computation of
4812:
4722:
3325:If there is an accepting computation for
3113:Possible transitions at computation step
421:{\displaystyle M=(Q,\Sigma ,s,F,\delta )}
293:Introduction to the Theory of Computation
4776:. In Ronald V. Book; Paul Young (eds.).
4398:
2466:{\displaystyle \bigvee _{q\in Q}Q_{q,k}}
340:
301:
249:This proof is based on the one given by
4772:Gary L. Peterson; John H. Reif (1979).
3818:) actually depends on the input string
66:to the Boolean satisfiability problem.
14:
5090:
4291:
4289:
4287:
2747:At least one head position at a time.
4865:{\displaystyle (A\lor B\lor C\lor D)}
4608:"Relations among complexity measures"
4427:[Universal search problems].
4419:
4303:. New York: Plenum. pp. 85–103.
4106:{\displaystyle O(\log(p(n))p(n)^{3})}
3769:{\displaystyle O(\log(p(n))p(n)^{3})}
2617:At most one head position at a time.
1831:Initial position of read/write head.
937:is the number of a computation step.
4474:Translation see appendix, p.399-400.
4446:(brute-force searches) algorithms".
4429:Problems of Information Transmission
4323:
4295:
1459:{\displaystyle -p(n)\leq i\leq p(n)}
863:{\displaystyle -p(n)\leq i\leq p(n)}
520:is the set of accepting states, and
4301:Complexity of Computer Computations
4284:
2056:At least one symbol per tape cell.
1609:Initial contents of the tape. For
1159:'s read/write head is at tape cell
24:
4906:
4449:Annals of the History of Computing
4036:'s time complexity is also known.
2549:
2527:
2313:
2291:
2015:
1947:At most one symbol per tape cell.
1873:
1845:
883:
572:
554:
455:
394:
260:polynomial-time many-one reduction
134:polynomial-time many-one reduction
25:
5109:
4168:{\displaystyle O(p(n)\log(p(n)))}
542:
468:is the alphabet of tape symbols,
136:). Cook and Karp each received a
4667:John Michael Robson (May 1991).
4648:John Michael Robson (Feb 1979).
4564:Claus-Peter Schnorr (Jan 1978).
1500:{\displaystyle 0\leq k\leq p(n)}
930:{\displaystyle 0\leq k\leq p(n)}
681:is the size of the instance and
198:non-deterministic Turing machine
122:Symposium on Theory of Computing
103:
5030:
5020:{\displaystyle (A\lor B\lor B)}
4821:
4788:
4765:
4731:
4660:
4641:
4425:"Универсальные задачи перебора"
4213:
724:, specify a Boolean expression
371:nondeterministic Turing machine
227:if there is some assignment of
130:list of 21 NP-complete problems
54:, and any problem in NP can be
32:computational complexity theory
5014:
4996:
4976:
4964:
4924:
4903:
4897:
4879:
4859:
4835:
4747:Information Processing Letters
4694:
4679:
4599:
4557:
4541:
4538:
4532:
4526:
4490:
4477:
4413:
4392:
4365:
4317:
4246:Boolean satisfiability problem
4162:
4159:
4156:
4150:
4144:
4135:
4129:
4123:
4100:
4091:
4084:
4078:
4075:
4069:
4063:
4054:
4003:
3997:
3946:
3940:
3914:
3908:
3763:
3754:
3747:
3741:
3738:
3732:
3726:
3717:
3674:
3665:
3658:
3652:
3629:
3626:
3620:
3608:
3585:
3576:
3569:
3563:
3303:
3297:
3236:
3230:
3187:
3178:
3171:
3165:
3098:
3092:
3058:
2949:
2938:
2935:
2907:
2901:
2889:
2886:
2874:
2871:
2808:
2781:
2772:
2765:
2759:
2712:
2706:
2691:
2685:
2651:
2642:
2635:
2629:
2504:
2501:
2495:
2489:
2477:At least one state at a time.
2408:
2405:
2399:
2393:
2268:
2259:
2252:
2246:
2171:
2090:
2081:
2074:
2068:
1981:
1972:
1965:
1959:
1714:
1711:
1705:
1699:
1667:, outside of the actual input
1494:
1488:
1453:
1447:
1432:
1426:
1389:Define the Boolean expression
1371:
1368:
1362:
1356:
1233:
1224:
1217:
1211:
1088:
1079:
1072:
1066:
924:
918:
857:
851:
836:
830:
648:
642:
599:
563:
557:
548:
536:
533:
415:
385:
297:in the Knowledge article on NP
253:, pp. 38–44, Section 2.6.
180:
44:Boolean satisfiability problem
13:
1:
4814:10.1016/S0898-1221(00)00333-3
4774:"Multiple-person alternation"
4277:
4039:
2381:At most one state at a time.
4759:10.1016/0020-0190(88)90152-4
4738:Stephen A. Cook (Jan 1988).
4724:10.1016/0304-3975(91)90177-4
4711:Theoretical Computer Science
4224:deterministic Turing machine
4204:logarithmic space complexity
3635:{\displaystyle O(\log p(n))}
3385:is satisfiable by assigning
889:{\displaystyle j\in \Sigma }
513:{\displaystyle F\subseteq Q}
309:showing Cook's reduction of
98:theoretical computer science
64:deterministic Turing machine
7:
4437:Translated into English by
4264:solved by heuristic methods
4196:polynomial space complexity
3680:{\displaystyle O(p(n)^{3})}
3642:. The number of clauses is
3591:{\displaystyle O(p(n)^{2})}
3193:{\displaystyle O(p(n)^{2})}
2787:{\displaystyle O(p(n)^{2})}
2657:{\displaystyle O(p(n)^{3})}
2274:{\displaystyle O(p(n)^{2})}
2096:{\displaystyle O(p(n)^{2})}
1987:{\displaystyle O(p(n)^{2})}
1239:{\displaystyle O(p(n)^{2})}
1094:{\displaystyle O(p(n)^{2})}
295:, section 7.3., as well as
69:The theorem is named after
10:
5114:
4700:{\displaystyle O(T\log T)}
4184:quantified Boolean formula
3779:Only the first table row (
1587:initially contains symbol
701:is a polynomial function.
196:if it can be decided by a
5052:W. H. Freeman and Company
4982:{\displaystyle (A\lor B)}
4784:. IEEE. pp. 348–363.
4374:SIAM Journal on Computing
3811:{\displaystyle T_{i,j,0}}
3417:{\displaystyle T_{i,j,k}}
3133:when head is at position
3104:{\displaystyle k<p(n)}
1558:{\displaystyle T_{i,j,0}}
985:{\displaystyle T_{i,j,k}}
661:computation steps, where
2608:{\displaystyle i\neq i'}
2372:{\displaystyle q\neq q'}
2225:{\displaystyle j\neq j'}
1938:{\displaystyle j\neq j'}
1634:{\displaystyle i>n-1}
946:Intended interpretation
285:in polynomial time by a
274:in polynomial time by a
251:Garey & Johnson 1979
243:
223:. Such an expression is
4547:{\displaystyle O(p(n))}
4462:10.1109/MAHC.1984.10036
4250:conjunctive normal form
4192:existential quantifiers
3483:{\displaystyle Q_{i,k}}
3450:{\displaystyle H_{i,k}}
2510:{\displaystyle O(p(n))}
2414:{\displaystyle O(p(n))}
1820:{\displaystyle H_{0,0}}
1756:{\displaystyle Q_{s,0}}
1720:{\displaystyle O(p(n))}
1377:{\displaystyle O(p(n))}
1275:{\displaystyle Q_{q,k}}
1130:{\displaystyle H_{i,k}}
461:{\displaystyle \Sigma }
234:
5021:
4983:
4951:
4931:
4866:
4701:
4548:
4510:
4268:mathematical logicians
4169:
4107:
4030:
4010:
3977:
3953:
3921:
3892:
3872:
3852:
3832:
3812:
3770:
3701:
3681:
3636:
3592:
3544:
3524:
3504:
3484:
3451:
3418:
3379:
3359:
3339:
3310:
3277:
3194:
3147:
3127:
3105:
3069:
2788:
2737:
2658:
2609:
2577:
2511:
2467:
2415:
2373:
2341:
2275:
2226:
2194:
2097:
2046:
1988:
1939:
1907:
1821:
1781:
1757:
1721:
1681:
1661:
1660:{\displaystyle i<0}
1635:
1601:
1581:
1559:
1501:
1460:
1403:
1378:
1338:
1318:
1298:
1276:
1240:
1193:
1173:
1153:
1131:
1095:
1048:
1028:
1008:
986:
931:
896:is a tape symbol, and
890:
864:
811:
810:{\displaystyle q\in Q}
782:
762:
738:
718:
695:
675:
655:
626:
606:
514:
494:is the initial state,
488:
487:{\displaystyle s\in Q}
462:
448:is the set of states,
442:
422:
366:
359:
338:
323:
77:. The proof is due to
5022:
4984:
4952:
4932:
4867:
4702:
4627:10.1145/322123.322138
4585:10.1145/322047.322060
4549:
4511:
4483:This column uses the
4341:10.1145/800157.805047
4188:universal quantifiers
4170:
4108:
4031:
4011:
3978:
3954:
3922:
3893:
3873:
3853:
3833:
3813:
3771:
3702:
3682:
3637:
3593:
3545:
3525:
3505:
3485:
3452:
3419:
3380:
3360:
3340:
3311:
3278:
3195:
3148:
3128:
3106:
3070:
2789:
2738:
2659:
2610:
2578:
2512:
2468:
2416:
2374:
2342:
2276:
2227:
2195:
2098:
2047:
1989:
1940:
1908:
1822:
1782:
1758:
1722:
1682:
1662:
1636:
1602:
1582:
1560:
1502:
1461:
1404:
1379:
1339:
1319:
1299:
1277:
1241:
1194:
1174:
1154:
1132:
1096:
1049:
1029:
1009:
987:
932:
891:
865:
812:
783:
763:
739:
719:
696:
676:
656:
627:
607:
515:
489:
463:
443:
423:
360:
344:
324:
305:
50:. That is, it is in
4993:
4961:
4941:
4876:
4832:
4673:
4520:
4500:
4335:. pp. 151–158.
4117:
4048:
4020:
4009:{\displaystyle p(n)}
3991:
3967:
3952:{\displaystyle p(n)}
3934:
3920:{\displaystyle p(n)}
3902:
3882:
3862:
3842:
3822:
3783:
3711:
3691:
3646:
3602:
3557:
3534:
3514:
3494:
3461:
3428:
3389:
3369:
3349:
3329:
3309:{\displaystyle p(n)}
3291:
3207:
3159:
3137:
3117:
3080:
2801:
2753:
2671:
2623:
2588:
2524:
2483:
2428:
2387:
2352:
2288:
2240:
2205:
2110:
2062:
2001:
1953:
1918:
1842:
1798:
1771:
1734:
1693:
1671:
1645:
1613:
1591:
1571:
1530:
1470:
1417:
1393:
1350:
1344:of the computation.
1328:
1308:
1288:
1253:
1205:
1199:of the computation.
1183:
1163:
1143:
1108:
1060:
1054:of the computation.
1038:
1018:
998:
957:
900:
874:
870:is a tape position,
821:
817:is a machine state,
795:
772:
752:
744:that is satisfiable
728:
708:
685:
665:
654:{\displaystyle p(n)}
636:
616:
524:
498:
472:
452:
432:
376:
349:
313:
4989:can be replaced by
4440:Trakhtenbrot, B. A.
4272:P versus NP problem
4248:for expressions in
3858:and on the machine
307:Commutative diagram
94:P versus NP problem
5017:
4979:
4947:
4927:
4862:
4778:Proc. 20th Annual
4697:
4615:Journal of the ACM
4573:Journal of the ACM
4544:
4506:
4180:complexity classes
4165:
4103:
4026:
4006:
3973:
3949:
3917:
3888:
3868:
3848:
3828:
3808:
3766:
3697:
3677:
3632:
3588:
3540:
3520:
3500:
3480:
3447:
3414:
3375:
3355:
3335:
3306:
3273:
3256:
3240:
3190:
3143:
3123:
3101:
3065:
3063:
2948:
2784:
2733:
2716:
2654:
2605:
2573:
2507:
2463:
2446:
2411:
2369:
2337:
2271:
2222:
2190:
2093:
2042:
2019:
1984:
1935:
1903:
1817:
1777:
1753:
1717:
1677:
1657:
1631:
1597:
1577:
1555:
1497:
1456:
1399:
1374:
1334:
1314:
1294:
1272:
1236:
1189:
1169:
1149:
1127:
1091:
1044:
1024:
1004:
994:True if tape cell
982:
927:
886:
860:
807:
778:
758:
734:
714:
691:
671:
651:
622:
602:
510:
484:
458:
438:
418:
367:
355:
339:
319:
213:Boolean expression
171:universal problems
42:, states that the
36:Cook–Levin theorem
18:Cook-Levin theorem
5042:Johnson, David S.
5038:Garey, Michael R.
4950:{\displaystyle Z}
4656:. pp. 62–70.
4509:{\displaystyle n}
4220:logarithmic space
4029:{\displaystyle M}
3976:{\displaystyle M}
3891:{\displaystyle M}
3871:{\displaystyle M}
3851:{\displaystyle n}
3831:{\displaystyle I}
3700:{\displaystyle B}
3543:{\displaystyle I}
3523:{\displaystyle M}
3503:{\displaystyle B}
3378:{\displaystyle B}
3358:{\displaystyle I}
3338:{\displaystyle M}
3323:
3322:
3241:
3210:
3146:{\displaystyle i}
3126:{\displaystyle k}
3046:
3032:
3004:
2971:
2881:
2674:
2431:
2004:
1780:{\displaystyle M}
1767:Initial state of
1680:{\displaystyle I}
1600:{\displaystyle j}
1580:{\displaystyle i}
1402:{\displaystyle B}
1387:
1386:
1337:{\displaystyle k}
1317:{\displaystyle q}
1297:{\displaystyle M}
1192:{\displaystyle k}
1172:{\displaystyle i}
1152:{\displaystyle M}
1047:{\displaystyle k}
1027:{\displaystyle j}
1007:{\displaystyle i}
781:{\displaystyle I}
761:{\displaystyle M}
737:{\displaystyle B}
717:{\displaystyle I}
694:{\displaystyle p}
674:{\displaystyle n}
625:{\displaystyle M}
441:{\displaystyle Q}
358:{\displaystyle M}
322:{\displaystyle M}
287:non-deterministic
221:Boolean operators
217:Boolean variables
16:(Redirected from
5105:
5082:
5081:
5034:
5028:
5026:
5024:
5023:
5018:
4988:
4986:
4985:
4980:
4956:
4954:
4953:
4948:
4936:
4934:
4933:
4928:
4871:
4869:
4868:
4863:
4825:
4819:
4818:
4816:
4807:(7–8): 957–992.
4792:
4786:
4785:
4769:
4763:
4762:
4744:
4735:
4729:
4728:
4726:
4706:
4704:
4703:
4698:
4664:
4658:
4657:
4645:
4639:
4638:
4612:
4603:
4597:
4596:
4570:
4561:
4555:
4553:
4551:
4550:
4545:
4515:
4513:
4512:
4507:
4494:
4488:
4481:
4475:
4473:
4436:
4417:
4411:
4410:
4396:
4390:
4389:
4369:
4363:
4362:
4321:
4315:
4314:
4297:Karp, Richard M.
4293:
4228:complexity class
4174:
4172:
4171:
4166:
4112:
4110:
4109:
4104:
4099:
4098:
4035:
4033:
4032:
4027:
4015:
4013:
4012:
4007:
3982:
3980:
3979:
3974:
3958:
3956:
3955:
3950:
3926:
3924:
3923:
3918:
3897:
3895:
3894:
3889:
3877:
3875:
3874:
3869:
3857:
3855:
3854:
3849:
3837:
3835:
3834:
3829:
3817:
3815:
3814:
3809:
3807:
3806:
3775:
3773:
3772:
3767:
3762:
3761:
3706:
3704:
3703:
3698:
3686:
3684:
3683:
3678:
3673:
3672:
3641:
3639:
3638:
3633:
3597:
3595:
3594:
3589:
3584:
3583:
3549:
3547:
3546:
3541:
3529:
3527:
3526:
3521:
3509:
3507:
3506:
3501:
3489:
3487:
3486:
3481:
3479:
3478:
3456:
3454:
3453:
3448:
3446:
3445:
3423:
3421:
3420:
3415:
3413:
3412:
3384:
3382:
3381:
3376:
3364:
3362:
3361:
3356:
3344:
3342:
3341:
3336:
3315:
3313:
3312:
3307:
3282:
3280:
3279:
3274:
3272:
3271:
3255:
3239:
3199:
3197:
3196:
3191:
3186:
3185:
3152:
3150:
3149:
3144:
3132:
3130:
3129:
3124:
3110:
3108:
3107:
3102:
3074:
3072:
3071:
3066:
3064:
3057:
3056:
3044:
3040:
3030:
3015:
3014:
3002:
2998:
2982:
2981:
2969:
2947:
2928:
2917:
2870:
2869:
2845:
2844:
2826:
2825:
2793:
2791:
2790:
2785:
2780:
2779:
2742:
2740:
2739:
2734:
2732:
2731:
2715:
2663:
2661:
2660:
2655:
2650:
2649:
2614:
2612:
2611:
2606:
2604:
2582:
2580:
2579:
2574:
2572:
2571:
2564:
2545:
2544:
2516:
2514:
2513:
2508:
2472:
2470:
2469:
2464:
2462:
2461:
2445:
2420:
2418:
2417:
2412:
2378:
2376:
2375:
2370:
2368:
2346:
2344:
2343:
2338:
2336:
2335:
2328:
2309:
2308:
2280:
2278:
2277:
2272:
2267:
2266:
2231:
2229:
2228:
2223:
2221:
2199:
2197:
2196:
2191:
2189:
2188:
2170:
2169:
2156:
2134:
2133:
2102:
2100:
2099:
2094:
2089:
2088:
2051:
2049:
2048:
2043:
2041:
2040:
2018:
1993:
1991:
1990:
1985:
1980:
1979:
1944:
1942:
1941:
1936:
1934:
1912:
1910:
1909:
1904:
1902:
1901:
1894:
1869:
1868:
1826:
1824:
1823:
1818:
1816:
1815:
1786:
1784:
1783:
1778:
1762:
1760:
1759:
1754:
1752:
1751:
1726:
1724:
1723:
1718:
1686:
1684:
1683:
1678:
1666:
1664:
1663:
1658:
1640:
1638:
1637:
1632:
1606:
1604:
1603:
1598:
1586:
1584:
1583:
1578:
1564:
1562:
1561:
1556:
1554:
1553:
1510:
1509:
1506:
1504:
1503:
1498:
1465:
1463:
1462:
1457:
1408:
1406:
1405:
1400:
1383:
1381:
1380:
1375:
1343:
1341:
1340:
1335:
1323:
1321:
1320:
1315:
1303:
1301:
1300:
1295:
1281:
1279:
1278:
1273:
1271:
1270:
1245:
1243:
1242:
1237:
1232:
1231:
1198:
1196:
1195:
1190:
1178:
1176:
1175:
1170:
1158:
1156:
1155:
1150:
1136:
1134:
1133:
1128:
1126:
1125:
1100:
1098:
1097:
1092:
1087:
1086:
1053:
1051:
1050:
1045:
1033:
1031:
1030:
1025:
1014:contains symbol
1013:
1011:
1010:
1005:
991:
989:
988:
983:
981:
980:
940:
939:
936:
934:
933:
928:
895:
893:
892:
887:
869:
867:
866:
861:
816:
814:
813:
808:
787:
785:
784:
779:
767:
765:
764:
759:
743:
741:
740:
735:
723:
721:
720:
715:
704:For each input,
700:
698:
697:
692:
680:
678:
677:
672:
660:
658:
657:
652:
631:
629:
628:
623:
611:
609:
608:
603:
519:
517:
516:
511:
493:
491:
490:
485:
467:
465:
464:
459:
447:
445:
444:
439:
427:
425:
424:
419:
364:
362:
361:
356:
336:
332:
328:
326:
325:
320:
187:decision problem
38:, also known as
21:
5113:
5112:
5108:
5107:
5106:
5104:
5103:
5102:
5088:
5087:
5086:
5085:
5062:
5035:
5031:
4994:
4991:
4990:
4962:
4959:
4958:
4942:
4939:
4938:
4877:
4874:
4873:
4833:
4830:
4829:
4826:
4822:
4793:
4789:
4770:
4766:
4742:
4736:
4732:
4674:
4671:
4670:
4665:
4661:
4646:
4642:
4610:
4604:
4600:
4568:
4562:
4558:
4521:
4518:
4517:
4501:
4498:
4497:
4495:
4491:
4482:
4478:
4418:
4414:
4397:
4393:
4386:10.1137/0204037
4370:
4366:
4351:
4322:
4318:
4311:
4294:
4285:
4280:
4216:
4200:PSPACE-complete
4118:
4115:
4114:
4094:
4090:
4049:
4046:
4045:
4042:
4021:
4018:
4017:
3992:
3989:
3988:
3968:
3965:
3964:
3935:
3932:
3931:
3903:
3900:
3899:
3883:
3880:
3879:
3863:
3860:
3859:
3843:
3840:
3839:
3823:
3820:
3819:
3790:
3786:
3784:
3781:
3780:
3757:
3753:
3712:
3709:
3708:
3692:
3689:
3688:
3687:so the size of
3668:
3664:
3647:
3644:
3643:
3603:
3600:
3599:
3579:
3575:
3558:
3555:
3554:
3535:
3532:
3531:
3515:
3512:
3511:
3495:
3492:
3491:
3468:
3464:
3462:
3459:
3458:
3435:
3431:
3429:
3426:
3425:
3396:
3392:
3390:
3387:
3386:
3370:
3367:
3366:
3350:
3347:
3346:
3330:
3327:
3326:
3292:
3289:
3288:
3261:
3257:
3245:
3214:
3208:
3205:
3204:
3181:
3177:
3160:
3157:
3156:
3138:
3135:
3134:
3118:
3115:
3114:
3081:
3078:
3077:
3062:
3061:
3033:
3023:
3019:
2991:
2990:
2986:
2956:
2952:
2921:
2910:
2885:
2878:
2877:
2853:
2849:
2834:
2830:
2815:
2811:
2804:
2802:
2799:
2798:
2775:
2771:
2754:
2751:
2750:
2721:
2717:
2678:
2672:
2669:
2668:
2645:
2641:
2624:
2621:
2620:
2597:
2589:
2586:
2585:
2557:
2556:
2552:
2534:
2530:
2525:
2522:
2521:
2484:
2481:
2480:
2451:
2447:
2435:
2429:
2426:
2425:
2388:
2385:
2384:
2361:
2353:
2350:
2349:
2321:
2320:
2316:
2298:
2294:
2289:
2286:
2285:
2262:
2258:
2241:
2238:
2237:
2214:
2206:
2203:
2202:
2178:
2174:
2149:
2142:
2138:
2117:
2113:
2111:
2108:
2107:
2084:
2080:
2063:
2060:
2059:
2024:
2020:
2008:
2002:
1999:
1998:
1975:
1971:
1954:
1951:
1950:
1927:
1919:
1916:
1915:
1887:
1880:
1876:
1852:
1848:
1843:
1840:
1839:
1805:
1801:
1799:
1796:
1795:
1772:
1769:
1768:
1741:
1737:
1735:
1732:
1731:
1694:
1691:
1690:
1672:
1669:
1668:
1646:
1643:
1642:
1614:
1611:
1610:
1592:
1589:
1588:
1572:
1569:
1568:
1537:
1533:
1531:
1528:
1527:
1519:Interpretation
1471:
1468:
1467:
1418:
1415:
1414:
1394:
1391:
1390:
1351:
1348:
1347:
1329:
1326:
1325:
1309:
1306:
1305:
1289:
1286:
1285:
1260:
1256:
1254:
1251:
1250:
1227:
1223:
1206:
1203:
1202:
1184:
1181:
1180:
1164:
1161:
1160:
1144:
1141:
1140:
1115:
1111:
1109:
1106:
1105:
1082:
1078:
1061:
1058:
1057:
1039:
1036:
1035:
1019:
1016:
1015:
999:
996:
995:
964:
960:
958:
955:
954:
901:
898:
897:
875:
872:
871:
822:
819:
818:
796:
793:
792:
773:
770:
769:
753:
750:
749:
729:
726:
725:
709:
706:
705:
686:
683:
682:
666:
663:
662:
637:
634:
633:
617:
614:
613:
525:
522:
521:
499:
496:
495:
473:
470:
469:
453:
450:
449:
433:
430:
429:
377:
374:
373:
350:
347:
346:
337:, respectively.
334:
330:
314:
311:
310:
246:
237:
202:polynomial time
183:
167:search problems
140:for this work.
110:NP-completeness
108:The concept of
106:
60:polynomial time
28:
23:
22:
15:
12:
11:
5:
5111:
5101:
5100:
5084:
5083:
5060:
5029:
5016:
5013:
5010:
5007:
5004:
5001:
4998:
4978:
4975:
4972:
4969:
4966:
4946:
4926:
4923:
4920:
4917:
4914:
4911:
4908:
4905:
4902:
4899:
4896:
4893:
4890:
4887:
4884:
4881:
4861:
4858:
4855:
4852:
4849:
4846:
4843:
4840:
4837:
4820:
4787:
4764:
4753:(5): 269–270.
4730:
4717:(1): 141–149.
4696:
4693:
4690:
4687:
4684:
4681:
4678:
4659:
4640:
4621:(2): 361–381.
4598:
4579:(1): 136–145.
4556:
4543:
4540:
4537:
4534:
4531:
4528:
4525:
4505:
4489:
4485:big O notation
4476:
4456:(4): 384–400.
4431:(in Russian).
4412:
4405:(in Russian).
4391:
4380:(4): 431–442.
4364:
4349:
4316:
4309:
4282:
4281:
4279:
4276:
4215:
4212:
4164:
4161:
4158:
4155:
4152:
4149:
4146:
4143:
4140:
4137:
4134:
4131:
4128:
4125:
4122:
4102:
4097:
4093:
4089:
4086:
4083:
4080:
4077:
4074:
4071:
4068:
4065:
4062:
4059:
4056:
4053:
4041:
4038:
4025:
4005:
4002:
3999:
3996:
3972:
3948:
3945:
3942:
3939:
3916:
3913:
3910:
3907:
3887:
3867:
3847:
3827:
3805:
3802:
3799:
3796:
3793:
3789:
3765:
3760:
3756:
3752:
3749:
3746:
3743:
3740:
3737:
3734:
3731:
3728:
3725:
3722:
3719:
3716:
3696:
3676:
3671:
3667:
3663:
3660:
3657:
3654:
3651:
3631:
3628:
3625:
3622:
3619:
3616:
3613:
3610:
3607:
3587:
3582:
3578:
3574:
3571:
3568:
3565:
3562:
3539:
3519:
3499:
3477:
3474:
3471:
3467:
3444:
3441:
3438:
3434:
3411:
3408:
3405:
3402:
3399:
3395:
3374:
3354:
3334:
3321:
3320:
3317:
3305:
3302:
3299:
3296:
3285:
3283:
3270:
3267:
3264:
3260:
3254:
3251:
3248:
3244:
3238:
3235:
3232:
3229:
3226:
3223:
3220:
3217:
3213:
3201:
3200:
3189:
3184:
3180:
3176:
3173:
3170:
3167:
3164:
3154:
3142:
3122:
3111:
3100:
3097:
3094:
3091:
3088:
3085:
3075:
3060:
3055:
3052:
3049:
3043:
3039:
3036:
3029:
3026:
3022:
3018:
3013:
3010:
3007:
3001:
2997:
2994:
2989:
2985:
2980:
2977:
2974:
2968:
2965:
2962:
2959:
2955:
2951:
2946:
2943:
2940:
2937:
2934:
2931:
2927:
2924:
2920:
2916:
2913:
2909:
2906:
2903:
2900:
2897:
2894:
2891:
2888:
2884:
2880:
2879:
2876:
2873:
2868:
2865:
2862:
2859:
2856:
2852:
2848:
2843:
2840:
2837:
2833:
2829:
2824:
2821:
2818:
2814:
2810:
2807:
2806:
2795:
2794:
2783:
2778:
2774:
2770:
2767:
2764:
2761:
2758:
2748:
2745:
2743:
2730:
2727:
2724:
2720:
2714:
2711:
2708:
2705:
2702:
2699:
2696:
2693:
2690:
2687:
2684:
2681:
2677:
2665:
2664:
2653:
2648:
2644:
2640:
2637:
2634:
2631:
2628:
2618:
2615:
2603:
2600:
2596:
2593:
2583:
2570:
2567:
2563:
2560:
2555:
2551:
2548:
2543:
2540:
2537:
2533:
2529:
2518:
2517:
2506:
2503:
2500:
2497:
2494:
2491:
2488:
2478:
2475:
2473:
2460:
2457:
2454:
2450:
2444:
2441:
2438:
2434:
2422:
2421:
2410:
2407:
2404:
2401:
2398:
2395:
2392:
2382:
2379:
2367:
2364:
2360:
2357:
2347:
2334:
2331:
2327:
2324:
2319:
2315:
2312:
2307:
2304:
2301:
2297:
2293:
2282:
2281:
2270:
2265:
2261:
2257:
2254:
2251:
2248:
2245:
2235:
2232:
2220:
2217:
2213:
2210:
2200:
2187:
2184:
2181:
2177:
2173:
2168:
2165:
2162:
2159:
2155:
2152:
2148:
2145:
2141:
2137:
2132:
2129:
2126:
2123:
2120:
2116:
2104:
2103:
2092:
2087:
2083:
2079:
2076:
2073:
2070:
2067:
2057:
2054:
2052:
2039:
2036:
2033:
2030:
2027:
2023:
2017:
2014:
2011:
2007:
1995:
1994:
1983:
1978:
1974:
1970:
1967:
1964:
1961:
1958:
1948:
1945:
1933:
1930:
1926:
1923:
1913:
1900:
1897:
1893:
1890:
1886:
1883:
1879:
1875:
1872:
1867:
1864:
1861:
1858:
1855:
1851:
1847:
1836:
1835:
1832:
1829:
1827:
1814:
1811:
1808:
1804:
1792:
1791:
1788:
1776:
1765:
1763:
1750:
1747:
1744:
1740:
1728:
1727:
1716:
1713:
1710:
1707:
1704:
1701:
1698:
1688:
1676:
1656:
1653:
1650:
1630:
1627:
1624:
1621:
1618:
1607:
1596:
1576:
1565:
1552:
1549:
1546:
1543:
1540:
1536:
1524:
1523:
1520:
1517:
1514:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1398:
1385:
1384:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1345:
1333:
1313:
1293:
1282:
1269:
1266:
1263:
1259:
1247:
1246:
1235:
1230:
1226:
1222:
1219:
1216:
1213:
1210:
1200:
1188:
1168:
1148:
1137:
1124:
1121:
1118:
1114:
1102:
1101:
1090:
1085:
1081:
1077:
1074:
1071:
1068:
1065:
1055:
1043:
1023:
1003:
992:
979:
976:
973:
970:
967:
963:
951:
950:
947:
944:
926:
923:
920:
917:
914:
911:
908:
905:
885:
882:
879:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
806:
803:
800:
777:
757:
746:if and only if
733:
713:
690:
670:
650:
647:
644:
641:
621:
601:
598:
595:
592:
589:
586:
583:
580:
577:
574:
571:
568:
565:
562:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
529:
509:
506:
503:
483:
480:
477:
457:
437:
417:
414:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
354:
318:
289:Turing machine
278:Turing machine
245:
242:
236:
233:
215:that combines
182:
179:
149:oracle machine
145:Robert Solovay
105:
102:
40:Cook's theorem
26:
9:
6:
4:
3:
2:
5110:
5099:
5096:
5095:
5093:
5079:
5075:
5071:
5067:
5063:
5061:9780716710455
5057:
5053:
5049:
5048:
5043:
5039:
5033:
5011:
5008:
5005:
5002:
4999:
4973:
4970:
4967:
4944:
4921:
4918:
4915:
4912:
4909:
4900:
4894:
4891:
4888:
4885:
4882:
4856:
4853:
4850:
4847:
4844:
4841:
4838:
4824:
4815:
4810:
4806:
4802:
4798:
4791:
4783:
4781:
4775:
4768:
4760:
4756:
4752:
4748:
4741:
4734:
4725:
4720:
4716:
4712:
4708:
4691:
4688:
4685:
4682:
4676:
4663:
4655:
4651:
4644:
4636:
4632:
4628:
4624:
4620:
4616:
4609:
4602:
4594:
4590:
4586:
4582:
4578:
4574:
4567:
4560:
4535:
4529:
4523:
4503:
4493:
4486:
4480:
4471:
4467:
4463:
4459:
4455:
4451:
4450:
4445:
4441:
4435:(3): 115–116.
4434:
4430:
4426:
4422:
4421:Levin, Leonid
4416:
4408:
4404:
4403:
4395:
4387:
4383:
4379:
4375:
4368:
4360:
4356:
4352:
4350:9781450374644
4346:
4342:
4338:
4334:
4330:
4326:
4325:Cook, Stephen
4320:
4312:
4310:0-306-30707-3
4306:
4302:
4298:
4292:
4290:
4288:
4283:
4275:
4273:
4269:
4265:
4260:
4258:
4253:
4251:
4247:
4242:
4240:
4236:
4231:
4229:
4225:
4221:
4211:
4209:
4205:
4201:
4197:
4193:
4189:
4185:
4181:
4176:
4153:
4147:
4141:
4138:
4132:
4126:
4120:
4095:
4087:
4081:
4072:
4066:
4060:
4057:
4051:
4037:
4023:
4000:
3994:
3986:
3970:
3962:
3943:
3937:
3928:
3911:
3905:
3885:
3865:
3845:
3825:
3803:
3800:
3797:
3794:
3791:
3787:
3777:
3758:
3750:
3744:
3735:
3729:
3723:
3720:
3714:
3694:
3669:
3661:
3655:
3649:
3623:
3617:
3614:
3611:
3605:
3580:
3572:
3566:
3560:
3551:
3537:
3517:
3497:
3475:
3472:
3469:
3465:
3442:
3439:
3436:
3432:
3409:
3406:
3403:
3400:
3397:
3393:
3372:
3352:
3332:
3318:
3300:
3294:
3286:
3284:
3268:
3265:
3262:
3258:
3252:
3249:
3246:
3242:
3233:
3227:
3224:
3221:
3218:
3215:
3211:
3203:
3202:
3182:
3174:
3168:
3162:
3155:
3140:
3120:
3112:
3095:
3089:
3086:
3083:
3076:
3053:
3050:
3047:
3041:
3037:
3034:
3027:
3024:
3020:
3016:
3011:
3008:
3005:
2999:
2995:
2992:
2987:
2983:
2978:
2975:
2972:
2966:
2963:
2960:
2957:
2953:
2944:
2941:
2932:
2929:
2925:
2922:
2918:
2914:
2911:
2904:
2898:
2895:
2892:
2882:
2866:
2863:
2860:
2857:
2854:
2850:
2846:
2841:
2838:
2835:
2831:
2827:
2822:
2819:
2816:
2812:
2797:
2796:
2776:
2768:
2762:
2756:
2749:
2746:
2744:
2728:
2725:
2722:
2718:
2709:
2703:
2700:
2697:
2694:
2688:
2682:
2679:
2675:
2667:
2666:
2646:
2638:
2632:
2626:
2619:
2616:
2601:
2598:
2594:
2591:
2584:
2568:
2565:
2561:
2558:
2553:
2546:
2541:
2538:
2535:
2531:
2520:
2519:
2498:
2492:
2486:
2479:
2476:
2474:
2458:
2455:
2452:
2448:
2442:
2439:
2436:
2432:
2424:
2423:
2402:
2396:
2390:
2383:
2380:
2365:
2362:
2358:
2355:
2348:
2332:
2329:
2325:
2322:
2317:
2310:
2305:
2302:
2299:
2295:
2284:
2283:
2263:
2255:
2249:
2243:
2236:
2233:
2218:
2215:
2211:
2208:
2201:
2185:
2182:
2179:
2175:
2166:
2163:
2160:
2157:
2153:
2150:
2146:
2143:
2139:
2135:
2130:
2127:
2124:
2121:
2118:
2114:
2106:
2105:
2085:
2077:
2071:
2065:
2058:
2055:
2053:
2037:
2034:
2031:
2028:
2025:
2021:
2012:
2009:
2005:
1997:
1996:
1976:
1968:
1962:
1956:
1949:
1946:
1931:
1928:
1924:
1921:
1914:
1898:
1895:
1891:
1888:
1884:
1881:
1877:
1870:
1865:
1862:
1859:
1856:
1853:
1849:
1838:
1837:
1833:
1830:
1828:
1812:
1809:
1806:
1802:
1794:
1793:
1789:
1774:
1766:
1764:
1748:
1745:
1742:
1738:
1730:
1729:
1708:
1702:
1696:
1689:
1674:
1654:
1651:
1648:
1628:
1625:
1622:
1619:
1616:
1608:
1594:
1574:
1566:
1550:
1547:
1544:
1541:
1538:
1534:
1526:
1525:
1521:
1518:
1515:
1512:
1511:
1508:
1491:
1485:
1482:
1479:
1476:
1473:
1450:
1444:
1441:
1438:
1435:
1429:
1423:
1420:
1412:
1396:
1365:
1359:
1353:
1346:
1331:
1311:
1291:
1283:
1267:
1264:
1261:
1257:
1249:
1248:
1228:
1220:
1214:
1208:
1201:
1186:
1166:
1146:
1138:
1122:
1119:
1116:
1112:
1104:
1103:
1083:
1075:
1069:
1063:
1056:
1041:
1021:
1001:
993:
977:
974:
971:
968:
965:
961:
953:
952:
948:
945:
942:
941:
938:
921:
915:
912:
909:
906:
903:
880:
877:
854:
848:
845:
842:
839:
833:
827:
824:
804:
801:
798:
789:
775:
755:
747:
731:
711:
702:
688:
668:
645:
639:
619:
593:
590:
587:
584:
581:
575:
569:
566:
560:
551:
545:
539:
530:
527:
507:
504:
501:
481:
478:
475:
435:
412:
409:
406:
403:
400:
397:
391:
388:
382:
379:
372:
352:
343:
316:
308:
304:
300:
298:
294:
290:
288:
284:
279:
277:
276:deterministic
273:
268:
263:
261:
255:
254:
252:
241:
232:
230:
226:
222:
218:
214:
210:
205:
203:
199:
195:
194:
188:
178:
176:
172:
168:
163:
161:
156:
154:
150:
146:
141:
139:
135:
131:
127:
123:
119:
115:
111:
104:Contributions
101:
99:
95:
91:
86:
84:
80:
76:
72:
67:
65:
61:
57:
53:
49:
45:
41:
37:
33:
19:
5045:
5032:
4823:
4804:
4800:
4790:
4777:
4767:
4750:
4746:
4733:
4714:
4710:
4662:
4653:
4649:
4643:
4618:
4614:
4601:
4576:
4572:
4559:
4492:
4479:
4453:
4447:
4443:
4432:
4428:
4415:
4409:: 1146–1148.
4406:
4400:
4394:
4377:
4373:
4367:
4332:
4319:
4300:
4261:
4256:
4254:
4243:
4235:Richard Karp
4232:
4217:
4214:Consequences
4177:
4043:
3961:constructive
3929:
3778:
3552:
3324:
1388:
1304:is in state
790:
748:the machine
703:
368:
292:
286:
282:
281:
275:
271:
270:
266:
264:
256:
248:
247:
238:
229:truth values
224:
208:
206:
190:
184:
170:
164:
160:Leonid Levin
157:
152:
142:
138:Turing Award
126:Richard Karp
118:Stephen Cook
107:
87:
79:Richard Karp
75:Leonid Levin
71:Stephen Cook
68:
39:
35:
29:
4208:NL-complete
1516:Conditions
1513:Expression
1411:conjunction
225:satisfiable
181:Definitions
116:. In 1971,
48:NP-complete
4278:References
4040:Complexity
3985:witnessing
3983:is known,
3963:: even if
3898:for up to
3553:There are
1567:Tape cell
1522:How many?
1409:to be the
949:How many?
943:Variables
272:verifiable
5078:247570676
5009:∨
5003:∨
4971:∨
4919:∨
4913:∨
4907:¬
4901:∧
4892:∨
4886:∨
4854:∨
4848:∨
4842:∨
4689:
4554:literals.
4142:
4061:
3724:
3615:
3530:on input
3345:on input
3250:∈
3243:⋁
3225:≤
3219:≤
3212:⋁
3035:σ
3017:∧
2984:∧
2945:δ
2942:∈
2923:σ
2899:σ
2883:⋁
2875:→
2861:σ
2847:∧
2828:∧
2701:≤
2695:≤
2680:−
2676:⋁
2595:≠
2550:¬
2547:∨
2528:¬
2440:∈
2433:⋁
2359:≠
2314:¬
2311:∨
2292:¬
2212:≠
2172:→
2136:∧
2016:Σ
2013:∈
2006:⋁
1925:≠
1874:¬
1871:∨
1846:¬
1626:−
1483:≤
1477:≤
1442:≤
1436:≤
1421:−
913:≤
907:≤
884:Σ
881:∈
846:≤
840:≤
825:−
802:∈
582:−
576:×
573:Σ
570:×
561:×
555:Σ
552:×
543:∖
531:⊆
528:δ
505:⊆
479:∈
456:Σ
413:δ
395:Σ
5092:Category
5044:(1979).
4937:, where
4423:(1973).
4327:(1971).
3038:′
2996:′
2926:′
2915:′
2602:′
2562:′
2366:′
2326:′
2219:′
2154:′
1932:′
1892:′
1324:at step
1284:True if
1179:at step
1139:True if
1034:at step
768:accepts
428:, where
283:solvable
267:verified
5070:0519066
4635:2432526
4593:1929802
4444:perebor
4359:7573663
3927:steps.
3365:, then
56:reduced
5076:
5068:
5058:
4782:(SFCS)
4633:
4591:
4470:950581
4468:
4357:
4347:
4307:
4182:. The
3045:
3031:
3003:
2970:
331:orange
219:using
175:P = NP
34:, the
4743:(PDF)
4631:S2CID
4611:(PDF)
4589:S2CID
4569:(PDF)
4466:S2CID
4355:S2CID
335:green
244:Proof
211:is a
62:by a
5074:OCLC
5056:ISBN
4669:"An
4345:ISBN
4305:ISBN
4190:and
3457:and
3087:<
1652:<
1641:and
1620:>
1466:and
333:and
280:and
235:Idea
114:USSR
83:Cook
73:and
4809:doi
4755:doi
4719:doi
4686:log
4623:doi
4581:doi
4458:doi
4382:doi
4337:doi
4139:log
4058:log
4016:of
3721:log
3707:is
3612:log
299:).
207:An
200:in
191:in
189:is
177:).
58:in
46:is
30:In
5094::
5072:.
5066:MR
5064:.
5054:.
5040:;
4805:41
4803:.
4799:.
4751:26
4749:.
4745:.
4715:82
4713:.
4709:.
4652:.
4629:.
4619:26
4617:.
4613:.
4587:.
4577:25
4575:.
4571:.
4464:.
4452:.
4407:14
4376:.
4353:.
4343:.
4331:.
4286:^
4274:.
4210:.
3424:,
3319:1
3316:.
3153:.
1834:1
1790:1
1787:.
1507::
788:.
262:.
204:.
193:NP
185:A
124:.
100:.
90:NP
85:.
52:NP
5080:.
5027:.
5015:)
5012:B
5006:B
5000:A
4997:(
4977:)
4974:B
4968:A
4965:(
4945:Z
4925:)
4922:D
4916:C
4910:Z
4904:(
4898:)
4895:Z
4889:B
4883:A
4880:(
4860:)
4857:D
4851:C
4845:B
4839:A
4836:(
4817:.
4811::
4761:.
4757::
4727:.
4721::
4695:)
4692:T
4683:T
4680:(
4677:O
4637:.
4625::
4595:.
4583::
4542:)
4539:)
4536:n
4533:(
4530:p
4527:(
4524:O
4504:n
4487:.
4472:.
4460::
4454:6
4433:9
4388:.
4384::
4378:4
4361:.
4339::
4313:.
4163:)
4160:)
4157:)
4154:n
4151:(
4148:p
4145:(
4136:)
4133:n
4130:(
4127:p
4124:(
4121:O
4101:)
4096:3
4092:)
4088:n
4085:(
4082:p
4079:)
4076:)
4073:n
4070:(
4067:p
4064:(
4055:(
4052:O
4024:M
4004:)
4001:n
3998:(
3995:p
3971:M
3947:)
3944:n
3941:(
3938:p
3915:)
3912:n
3909:(
3906:p
3886:M
3866:M
3846:n
3826:I
3804:0
3801:,
3798:j
3795:,
3792:i
3788:T
3764:)
3759:3
3755:)
3751:n
3748:(
3745:p
3742:)
3739:)
3736:n
3733:(
3730:p
3727:(
3718:(
3715:O
3695:B
3675:)
3670:3
3666:)
3662:n
3659:(
3656:p
3653:(
3650:O
3630:)
3627:)
3624:n
3621:(
3618:p
3609:(
3606:O
3586:)
3581:2
3577:)
3573:n
3570:(
3567:p
3564:(
3561:O
3538:I
3518:M
3498:B
3476:k
3473:,
3470:i
3466:Q
3443:k
3440:,
3437:i
3433:H
3410:k
3407:,
3404:j
3401:,
3398:i
3394:T
3373:B
3353:I
3333:M
3304:)
3301:n
3298:(
3295:p
3269:k
3266:,
3263:f
3259:Q
3253:F
3247:f
3237:)
3234:n
3231:(
3228:p
3222:k
3216:0
3188:)
3183:2
3179:)
3175:n
3172:(
3169:p
3166:(
3163:O
3141:i
3121:k
3099:)
3096:n
3093:(
3090:p
3084:k
3059:)
3054:1
3051:+
3048:k
3042:,
3028:,
3025:i
3021:T
3012:1
3009:+
3006:k
3000:,
2993:q
2988:Q
2979:1
2976:+
2973:k
2967:,
2964:d
2961:+
2958:i
2954:H
2950:(
2939:)
2936:)
2933:d
2930:,
2919:,
2912:q
2908:(
2905:,
2902:)
2896:,
2893:q
2890:(
2887:(
2872:)
2867:k
2864:,
2858:,
2855:i
2851:T
2842:k
2839:,
2836:q
2832:Q
2823:k
2820:,
2817:i
2813:H
2809:(
2782:)
2777:2
2773:)
2769:n
2766:(
2763:p
2760:(
2757:O
2729:k
2726:,
2723:i
2719:H
2713:)
2710:n
2707:(
2704:p
2698:i
2692:)
2689:n
2686:(
2683:p
2652:)
2647:3
2643:)
2639:n
2636:(
2633:p
2630:(
2627:O
2599:i
2592:i
2569:k
2566:,
2559:i
2554:H
2542:k
2539:,
2536:i
2532:H
2505:)
2502:)
2499:n
2496:(
2493:p
2490:(
2487:O
2459:k
2456:,
2453:q
2449:Q
2443:Q
2437:q
2409:)
2406:)
2403:n
2400:(
2397:p
2394:(
2391:O
2363:q
2356:q
2333:k
2330:,
2323:q
2318:Q
2306:k
2303:,
2300:q
2296:Q
2269:)
2264:2
2260:)
2256:n
2253:(
2250:p
2247:(
2244:O
2216:j
2209:j
2186:k
2183:,
2180:i
2176:H
2167:1
2164:+
2161:k
2158:,
2151:j
2147:,
2144:i
2140:T
2131:k
2128:,
2125:j
2122:,
2119:i
2115:T
2091:)
2086:2
2082:)
2078:n
2075:(
2072:p
2069:(
2066:O
2038:k
2035:,
2032:j
2029:,
2026:i
2022:T
2010:j
1982:)
1977:2
1973:)
1969:n
1966:(
1963:p
1960:(
1957:O
1929:j
1922:j
1899:k
1896:,
1889:j
1885:,
1882:i
1878:T
1866:k
1863:,
1860:j
1857:,
1854:i
1850:T
1813:0
1810:,
1807:0
1803:H
1775:M
1749:0
1746:,
1743:s
1739:Q
1715:)
1712:)
1709:n
1706:(
1703:p
1700:(
1697:O
1675:I
1655:0
1649:i
1629:1
1623:n
1617:i
1595:j
1575:i
1551:0
1548:,
1545:j
1542:,
1539:i
1535:T
1495:)
1492:n
1489:(
1486:p
1480:k
1474:0
1454:)
1451:n
1448:(
1445:p
1439:i
1433:)
1430:n
1427:(
1424:p
1397:B
1372:)
1369:)
1366:n
1363:(
1360:p
1357:(
1354:O
1332:k
1312:q
1292:M
1268:k
1265:,
1262:q
1258:Q
1234:)
1229:2
1225:)
1221:n
1218:(
1215:p
1212:(
1209:O
1187:k
1167:i
1147:M
1123:k
1120:,
1117:i
1113:H
1089:)
1084:2
1080:)
1076:n
1073:(
1070:p
1067:(
1064:O
1042:k
1022:j
1002:i
978:k
975:,
972:j
969:,
966:i
962:T
925:)
922:n
919:(
916:p
910:k
904:0
878:j
858:)
855:n
852:(
849:p
843:i
837:)
834:n
831:(
828:p
805:Q
799:q
776:I
756:M
732:B
712:I
689:p
669:n
649:)
646:n
643:(
640:p
620:M
600:)
597:}
594:1
591:+
588:,
585:1
579:{
567:Q
564:(
558:)
549:)
546:F
540:Q
537:(
534:(
508:Q
502:F
482:Q
476:s
436:Q
416:)
410:,
407:F
404:,
401:s
398:,
392:,
389:Q
386:(
383:=
380:M
365:.
353:M
317:M
153:A
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.