1921:
2799:
2958:
between the lower and upper time bound in the hierarchy theorem can be traced to the efficiency of the device used in the proof, namely a universal program that maintains a step-count. This can be done more efficiently on certain computational models. The sharpest results, presented below, have been
1741:
2636:
2152:
1545:
209:
1207:
1670:
66:, there is a strictly larger time-bounded complexity class, and so the time-bounded hierarchy of complexity classes does not completely collapse. More precisely, the time hierarchy theorem for deterministic Turing machines states that for all
887:
2641:
1916:{\displaystyle {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {2n+1}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f(n)\right).}
350:
520:
1454:
2505:
2875:
However, the time hierarchy theorems provide no means to relate deterministic and non-deterministic complexity, or time and space complexity, so they cast no light on the great unsolved questions of
2325:
2510:
583:
2237:
2069:
1465:
1020:
397:
in 1978. Finally in 1983, Stanislav Ε½Γ‘k achieved the same result with the simple proof taught today. The time hierarchy theorem for nondeterministic Turing machines states that if
3105:
83:
3053:
1079:
615:
1365:
1600:
968:
2956:
764:
376:
2794:{\displaystyle {\mathsf {DTIME}}\left(2^{n}\right)\subseteq {\mathsf {DTIME}}\left(o\left({\frac {2^{2n}}{2n}}\right)\right)\subsetneq {\mathsf {DTIME}}(2^{2n})}
3598:
31:. Informally, these theorems say that given more time, a Turing machine can solve more problems. For example, there are problems that can be solved with
3149:
2162:
The reader may have realised that the proof gives the weaker result because we have chosen a simple Turing machine simulation for which we know that
265:
431:
3021:
Thus, a constant-factor increase in the time bound allows for solving more problems, in contrast with the situation for Turing machines (see
1381:
1054:+ 1)), as it is simpler but illustrates the proof idea. See the bottom of this section for information on how to extend the proof to
2993:) is a time-constructible function, then there exists a decision problem which cannot be solved in worst-case deterministic time
2458:
2631:{\displaystyle {\mathsf {P}}\subseteq {\mathsf {DTIME}}(2^{n})\subsetneq {\mathsf {DTIME}}(2^{2n})\subseteq {\mathsf {EXPTIME}}}
2248:
3593:
3423:
1073:
To prove this, we first define the language of the encodings of machines and their inputs which cause them to halt within f
552:
2168:
530:. A similar theorem is not known for time-bounded probabilistic complexity classes, unless the class also has one bit of
1289:|) and then writing out a row of 0s of that length, and then using this row of 0s as a "clock" or "counter" to simulate
3571:
3548:
3439:
Sudborough, Ivan H.; Zalcberg, A. (1976). "On
Families of Languages Defined by Time-Bounded Random Access Machines".
3390:
2876:
2147:{\displaystyle H_{f}\notin {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right).}
382:
20:
1540:{\displaystyle H_{f}\notin {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right)}
2973:
model whose programs operate on a binary tree that is always accessed via its root. This model, introduced by
59:
58:
in 1965. It was improved a year later when F. C. Hennie and
Richard E. Stearns improved the efficiency of the
678:
204:{\displaystyle {\mathsf {DTIME}}\left(o\left(f(n)\right)\right)\subsetneq {\mathsf {DTIME}}(f(n){\log f(n)})}
980:
3066:
1293:
for at most that many steps. At each step, the simulating machine needs to look through the definition of
1202:{\displaystyle H_{f}=\left\{(,x)\ |\ M\ {\text{accepts}}\ x\ {\text{in}}\ f(|x|)\ {\text{steps}}\right\}.}
1212:
Notice here that this is a time-class. It is the set of pairs of machines and inputs to those machines (
3032:
633:
with non-negative integer coefficients are time-constructible, as are exponential functions such as 2.
592:
1316:
1665:{\displaystyle {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right).}
2414:
The time hierarchy theorems guarantee that the deterministic and non-deterministic versions of the
1243:
is its input (the initial contents of its tape). denotes an input that encodes the Turing machine
929:
3116:
882:{\displaystyle {\mathsf {DTIME}}(o(f(n)))\subsetneq {\mathsf {DTIME}}\left(f(n)\log f(n)\right).}
527:
3559:
3022:
2926:
547:
543:
67:
2964:
2415:
355:
3373:
Fortnow, L.; Santhanam, R. (2004). "Hierarchy
Theorems for Probabilistic Polynomial Time".
3188:
2970:
3055:, there exists a decision problem which cannot be solved in worst-case deterministic time
2364:)), then there exists a decision problem which cannot be solved in non-deterministic time
8:
531:
2977:
is stronger than a deterministic Turing machine but weaker than a random-access machine.
694:
3483:
3396:
3322:
3284:
3237:
3203:
3176:
3140:
2840:
is a practical class of algorithms. If such a collapse did occur, we could deduce that
2833:
390:
51:
3514:
3567:
3544:
3537:
3419:
3386:
3358:
3341:
3314:
3229:
3168:
414:
3326:
3510:
3487:
3475:
3448:
3400:
3378:
3353:
3304:
3263:
3241:
3219:
3158:
1297:
to decide what the next action would be. It is safe to say that this takes at most
723:
389:
in 1972. It was improved to its current form via a complex proof by Joel
Seiferas,
228:
63:
1305:) operations (since it is known that a simulation of a machine of time complexity
3288:
3184:
3136:
2880:
2438:
394:
55:
3532:
2420:
2353:
586:
247:
notation, referring to the set of decision problems solvable in asymptotically
232:
47:
28:
3029:
of polynomial growth rate (but more than linear), it is the case that for all
3587:
3318:
3233:
3172:
2974:
3255:
2242:
It is known that a more efficient simulation exists which establishes that
386:
345:{\displaystyle {\mathsf {DTIME}}(n^{a})\subsetneq {\mathsf {DTIME}}(n^{b})}
3479:
3309:
3292:
3268:
3224:
3207:
3382:
515:{\displaystyle {\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n))}
3501:
Ben-Amram, Amir M. (2003). "Tighter constant-factor time hierarchies".
3180:
630:
3260:
Proceedings of the fourth annual ACM symposium on Theory of computing
1565:
is in this time complexity class, and we will reach a contradiction.
3452:
3262:. STOC '72. Denver, Colorado, United States: ACM. pp. 187β192.
3163:
3144:
2444:
244:
62:. Consequent to the theorem, for every deterministic time-bounded
2426:
2808:
requiring arbitrarily large exponents to solve; in other words,
2895:
1449:{\displaystyle H_{f}\in {\mathsf {TIME}}\left(f(m)^{3}\right).}
1575:
is in this time complexity class, then there exists a machine
3375:
45th Annual IEEE Symposium on
Foundations of Computer Science
3025:). Moreover, Ben-Amram proved that, in the above models, for
2432:
2382:
665:)). We do this by constructing a machine which cannot be in
216:
3258:(1972). "A hierarchy for nondeterministic time complexity".
3578:
Section 7.2: The
Hierarchy Theorem, pp. 143–146.
2500:{\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}
2331:
27:
are important statements about time-bounded computation on
1687:
on the tuple (, ), ie. M is simulated on its own code by
16:
Given more time, a Turing machine can solve more problems
2320:{\displaystyle H_{f}\in {\mathsf {TIME}}(f(m)\log f(m))}
1030:
We include here a proof of a weaker result, namely that
726:
which cannot be solved in worst-case deterministic time
722:) is a time-constructible function, then there exists a
3555:
Pages 310–313 of section 9.1: Hierarchy theorems.
2804:
The theorem also guarantees that there are problems in
907:, since smaller functions are never time-constructible.
700:
3558:
2981:
For these models, the theorem has the following form:
738:)) but can be solved in worst-case deterministic time
585:
is time-constructible if there exists a deterministic
578:{\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }
3293:"Separating Nondeterministic Time Complexity Classes"
3069:
3035:
2929:
2644:
2513:
2461:
2251:
2171:
2072:
1744:
1603:
1468:
1384:
1319:
1082:
983:
932:
767:
595:
555:
434:
358:
268:
86:
3372:
3282:
2232:{\displaystyle H_{f}\in {\mathsf {TIME}}(f(m)^{3}).}
3536:
3438:
3208:"Two-Tape Simulation of Multitape Turing Machines"
3099:
3047:
2950:
2793:
2630:
2499:
2319:
2231:
2146:
1915:
1664:
1539:
1448:
1359:
1201:
1014:
962:
881:
609:
577:
514:
370:
344:
203:
3150:Transactions of the American Mathematical Society
1579:which, given some machine description and input
3585:
3135:
1558:, we get the desired result. Let us assume that
3145:"On the computational complexity of algorithms"
3531:
2824:. For example, there are problems solvable in
2372:) but can be solved in non-deterministic time
1938:accepts its own description as input, we get:
1683:, which takes a machine description and runs
3201:
2918:
1934:the length of ) and ask the question whether
617:, if the machine is started with an input of
3599:Theorems in computational complexity theory
653:)) is strictly larger than some time class
3157:. American Mathematical Society: 285β306.
3539:Introduction to the Theory of Computation
3500:
3472:25th Symposium on the Theory of Computing
3466:Jones, Neil D. (1993). "Constant factors
3416:Introduction to the Theory of Computation
3357:
3308:
3267:
3223:
3162:
1265:by way of a deterministic Turing machine
1258:We know that we can decide membership of
603:
571:
563:
526:The analogous theorems for space are the
378:, so we have an infinite time hierarchy.
2848:, since it is a well-known theorem that
2418:are genuine hierarchies: in other words
2380:). In other words, the complexity class
2344:) is a time-constructible function, and
2332:Non-deterministic time hierarchy theorem
405:) is a time-constructible function, and
48:deterministic multi-tape Turing machines
3063:) but can be solved in worst-case time
3001:) but can be solved in worst-case time
1239:is a deterministic Turing machine, and
681:. We then show that the machine is in
3586:
3413:
3303:(1). New York, NY, USA: ACM: 146β167.
3218:(4). New York, NY, USA: ACM: 533β546.
2767:
2764:
2761:
2758:
2755:
2699:
2696:
2693:
2690:
2687:
2659:
2656:
2653:
2650:
2647:
2623:
2620:
2617:
2614:
2611:
2608:
2605:
2576:
2573:
2570:
2567:
2564:
2538:
2535:
2532:
2529:
2526:
2516:
2492:
2489:
2486:
2483:
2480:
2477:
2474:
2464:
2276:
2273:
2270:
2267:
2196:
2193:
2190:
2187:
2097:
2094:
2091:
2088:
1883:
1880:
1877:
1874:
1814:
1811:
1808:
1805:
1756:
1753:
1750:
1747:
1615:
1612:
1609:
1606:
1493:
1490:
1487:
1484:
1409:
1406:
1403:
1400:
1015:{\displaystyle o\left(n\log n\right).}
831:
828:
825:
822:
819:
782:
779:
776:
773:
770:
641:We need to prove that some time class
489:
486:
483:
480:
477:
449:
446:
443:
440:
437:
321:
318:
315:
312:
309:
283:
280:
277:
274:
271:
158:
155:
152:
149:
146:
101:
98:
95:
92:
89:
3465:
3352:(3). Elsevier Science B.V.: 327β333.
1459:The rest of the proof will show that
3254:
3100:{\displaystyle (1+\varepsilon )f(n)}
914:There are problems solvable in time
701:Deterministic time hierarchy theorem
3339:
2832:time. This is one argument against
1371:| is the length of the encoding of
621:ones, it will halt after precisely
227:)) denotes the complexity class of
13:
3525:
3418:(3rd ed.). CENGAGE learning.
2059:We thus conclude that the machine
2014:(which we know it does in at most
1949:(which we know it does in at most
542:Both theorems use the notion of a
14:
3610:
3342:"A Turing machine time hierarchy"
3048:{\displaystyle \varepsilon >0}
2801:from the time hierarchy theorem.
636:
610:{\displaystyle n\in \mathbb {N} }
243:)). The left-hand class involves
3566:(1st ed.). Addison Wesley.
3414:Sipser, Michael (27 June 2012).
1360:{\displaystyle O(T(n)\cdot |M|)}
383:nondeterministic Turing machines
3494:
3340:Ε½Γ‘k, Stanislav (October 1983).
2877:computational complexity theory
2409:
2022:) operations), this means that
1723:plus some delimiter symbol, so
1583:, decides whether the tuple (,
1367:on a multitape machine, where |
381:The time hierarchy theorem for
262:In particular, this shows that
46:The time hierarchy theorem for
21:computational complexity theory
3503:Information Processing Letters
3459:
3432:
3407:
3366:
3333:
3276:
3248:
3195:
3129:
3094:
3088:
3082:
3070:
2945:
2939:
2788:
2772:
2597:
2581:
2556:
2543:
2314:
2311:
2305:
2293:
2287:
2281:
2223:
2214:
2207:
2201:
1983:, and so by the definition of
1926:Now if we feed as input into
1902:
1896:
1707:is the length of the input to
1679:to construct another machine,
1429:
1422:
1354:
1350:
1342:
1335:
1329:
1323:
1313:) for can be achieved in time
1180:
1176:
1168:
1164:
1126:
1119:
1110:
1104:
1101:
942:
936:
868:
862:
850:
844:
811:
808:
805:
799:
793:
787:
567:
509:
506:
500:
494:
469:
466:
460:
454:
339:
326:
301:
288:
198:
194:
188:
175:
169:
163:
128:
122:
1:
3515:10.1016/S0020-0190(03)00253-9
3122:
1281:) steps by first calculating
537:
3594:Structural complexity theory
3359:10.1016/0304-3975(83)90015-4
3346:Theoretical Computer Science
2860:)) is strictly contained in
2157:
1715:(the length of the input to
1251:be the size of the tuple (,
963:{\displaystyle f(n)=n\log n}
705:
68:time-constructible functions
7:
3110:
544:time-constructible function
10:
3615:
2919:Sharper hierarchy theorems
1969:) steps), this means that
1550:so that if we substitute 2
926:. This follows by setting
3441:SIAM Journal on Computing
2951:{\displaystyle \log f(n)}
2923:The gap of approximately
2394:)) is a strict subset of
1042:)) is a strict subset of
385:was originally proven by
3564:Computational Complexity
1976:(, ), so (, ) is not in
1699:rejects, and rejects if
1025:
528:space hierarchy theorems
60:Universal Turing machine
3117:Space hierarchy theorem
2063:does not exist, and so
2055:) steps. Contradiction.
2002:) steps. Contradiction.
1735:s running time is thus
712:Time Hierarchy Theorem.
25:time hierarchy theorems
3560:Christos Papadimitriou
3101:
3049:
3023:Linear speedup theorem
3019:
2952:
2836:, the convention that
2795:
2632:
2501:
2321:
2233:
2148:
1917:
1666:
1541:
1450:
1361:
1220:) so that the machine
1203:
1016:
964:
891:
883:
611:
579:
516:
372:
371:{\displaystyle a<b}
346:
205:
3480:10.1145/167088.167244
3310:10.1145/322047.322061
3269:10.1145/800152.804913
3225:10.1145/321356.321362
3102:
3050:
2983:
2965:random-access machine
2953:
2812:does not collapse to
2796:
2633:
2502:
2416:exponential hierarchy
2322:
2234:
2149:
1918:
1667:
1542:
1451:
1362:
1204:
1017:
965:
884:
709:
612:
580:
517:
373:
347:
206:
43:is the input length.
3383:10.1109/FOCS.2004.33
3067:
3033:
3009:) for some constant
2971:programming language
2927:
2642:
2511:
2459:
2249:
2169:
2070:
1994:does not accept in
1990:, this implies that
1930:itself (which makes
1742:
1601:
1466:
1382:
1317:
1080:
981:
930:
765:
593:
589:such that for every
553:
432:
356:
266:
84:
50:was first proven by
3285:Fischer, Michael J.
3283:Seiferas, Joel I.;
1957:) operations since
3543:. PWS Publishing.
3097:
3045:
2948:
2915:are equal or not.
2791:
2628:
2497:
2317:
2229:
2144:
1913:
1662:
1537:
1446:
1357:
1199:
1012:
960:
879:
607:
575:
512:
368:
342:
201:
52:Richard E. Stearns
3425:978-1-133-18779-0
2739:
2126:
1961:halts on (, ) in
1854:
1785:
1644:
1522:
1375:), we have that:
1269:, that simulates
1189:
1185:
1160:
1156:
1152:
1146:
1142:
1138:
1132:
1124:
695:simulator machine
231:solvable in time
229:decision problems
3606:
3577:
3554:
3542:
3519:
3518:
3498:
3492:
3491:
3463:
3457:
3456:
3436:
3430:
3429:
3411:
3405:
3404:
3370:
3364:
3363:
3361:
3337:
3331:
3330:
3312:
3291:(January 1978).
3289:Meyer, Albert R.
3280:
3274:
3273:
3271:
3256:Cook, Stephen A.
3252:
3246:
3245:
3227:
3206:(October 1966).
3199:
3193:
3192:
3166:
3133:
3106:
3104:
3103:
3098:
3054:
3052:
3051:
3046:
2957:
2955:
2954:
2949:
2820:) for any fixed
2800:
2798:
2797:
2792:
2787:
2786:
2771:
2770:
2749:
2745:
2744:
2740:
2738:
2730:
2729:
2717:
2703:
2702:
2681:
2677:
2676:
2663:
2662:
2637:
2635:
2634:
2629:
2627:
2626:
2596:
2595:
2580:
2579:
2555:
2554:
2542:
2541:
2520:
2519:
2506:
2504:
2503:
2498:
2496:
2495:
2468:
2467:
2326:
2324:
2323:
2318:
2280:
2279:
2261:
2260:
2238:
2236:
2235:
2230:
2222:
2221:
2200:
2199:
2181:
2180:
2153:
2151:
2150:
2145:
2140:
2136:
2135:
2131:
2127:
2119:
2101:
2100:
2082:
2081:
1922:
1920:
1919:
1914:
1909:
1905:
1887:
1886:
1868:
1864:
1863:
1859:
1855:
1850:
1836:
1818:
1817:
1799:
1795:
1794:
1790:
1786:
1778:
1760:
1759:
1671:
1669:
1668:
1663:
1658:
1654:
1653:
1649:
1645:
1637:
1619:
1618:
1546:
1544:
1543:
1538:
1536:
1532:
1531:
1527:
1523:
1515:
1497:
1496:
1478:
1477:
1455:
1453:
1452:
1447:
1442:
1438:
1437:
1436:
1413:
1412:
1394:
1393:
1366:
1364:
1363:
1358:
1353:
1345:
1208:
1206:
1205:
1200:
1195:
1191:
1190:
1187:
1183:
1179:
1171:
1158:
1157:
1154:
1150:
1144:
1143:
1140:
1136:
1130:
1129:
1122:
1092:
1091:
1021:
1019:
1018:
1013:
1008:
1004:
969:
967:
966:
961:
888:
886:
885:
880:
875:
871:
835:
834:
786:
785:
724:decision problem
616:
614:
613:
608:
606:
584:
582:
581:
576:
574:
566:
521:
519:
518:
513:
493:
492:
453:
452:
377:
375:
374:
369:
351:
349:
348:
343:
338:
337:
325:
324:
300:
299:
287:
286:
210:
208:
207:
202:
197:
162:
161:
140:
136:
135:
131:
105:
104:
64:complexity class
3614:
3613:
3609:
3608:
3607:
3605:
3604:
3603:
3584:
3583:
3574:
3551:
3528:
3526:Further reading
3523:
3522:
3499:
3495:
3464:
3460:
3453:10.1137/0205018
3437:
3433:
3426:
3412:
3408:
3393:
3377:. p. 316.
3371:
3367:
3338:
3334:
3281:
3277:
3253:
3249:
3202:Hennie, F. C.;
3200:
3196:
3164:10.2307/1994208
3134:
3130:
3125:
3113:
3068:
3065:
3064:
3034:
3031:
3030:
2928:
2925:
2924:
2921:
2834:Cobham's thesis
2779:
2775:
2754:
2753:
2731:
2722:
2718:
2716:
2712:
2708:
2704:
2686:
2685:
2672:
2668:
2664:
2646:
2645:
2643:
2640:
2639:
2604:
2603:
2588:
2584:
2563:
2562:
2550:
2546:
2525:
2524:
2515:
2514:
2512:
2509:
2508:
2473:
2472:
2463:
2462:
2460:
2457:
2456:
2412:
2334:
2266:
2265:
2256:
2252:
2250:
2247:
2246:
2217:
2213:
2186:
2185:
2176:
2172:
2170:
2167:
2166:
2160:
2118:
2114:
2110:
2106:
2102:
2087:
2086:
2077:
2073:
2071:
2068:
2067:
2038:
1988:
1981:
1892:
1888:
1873:
1872:
1837:
1835:
1831:
1827:
1823:
1819:
1804:
1803:
1777:
1773:
1769:
1765:
1761:
1746:
1745:
1743:
1740:
1739:
1636:
1632:
1628:
1624:
1620:
1605:
1604:
1602:
1599:
1598:
1592:
1573:
1563:
1514:
1510:
1506:
1502:
1498:
1483:
1482:
1473:
1469:
1467:
1464:
1463:
1432:
1428:
1418:
1414:
1399:
1398:
1389:
1385:
1383:
1380:
1379:
1349:
1341:
1318:
1315:
1314:
1263:
1224:accepts within
1186:
1175:
1167:
1153:
1139:
1125:
1100:
1096:
1087:
1083:
1081:
1078:
1077:
1028:
991:
987:
982:
979:
978:
931:
928:
927:
908:
840:
836:
818:
817:
769:
768:
766:
763:
762:
708:
703:
679:diagonalization
639:
602:
594:
591:
590:
570:
562:
554:
551:
550:
540:
476:
475:
436:
435:
433:
430:
429:
391:Michael Fischer
357:
354:
353:
352:if and only if
333:
329:
308:
307:
295:
291:
270:
269:
267:
264:
263:
178:
145:
144:
118:
114:
110:
106:
88:
87:
85:
82:
81:
56:Juris Hartmanis
29:Turing machines
17:
12:
11:
5:
3612:
3602:
3601:
3596:
3580:
3579:
3572:
3556:
3549:
3533:Michael Sipser
3527:
3524:
3521:
3520:
3493:
3458:
3447:(2): 217β230.
3431:
3424:
3406:
3391:
3365:
3332:
3275:
3247:
3204:Stearns, R. E.
3194:
3143:(1 May 1965).
3141:Stearns, R. E.
3127:
3126:
3124:
3121:
3120:
3119:
3112:
3109:
3096:
3093:
3090:
3087:
3084:
3081:
3078:
3075:
3072:
3044:
3041:
3038:
3013:(dependent on
2979:
2978:
2967:
2963:The unit-cost
2947:
2944:
2941:
2938:
2935:
2932:
2920:
2917:
2790:
2785:
2782:
2778:
2774:
2769:
2766:
2763:
2760:
2757:
2752:
2748:
2743:
2737:
2734:
2728:
2725:
2721:
2715:
2711:
2707:
2701:
2698:
2695:
2692:
2689:
2684:
2680:
2675:
2671:
2667:
2661:
2658:
2655:
2652:
2649:
2625:
2622:
2619:
2616:
2613:
2610:
2607:
2602:
2599:
2594:
2591:
2587:
2583:
2578:
2575:
2572:
2569:
2566:
2561:
2558:
2553:
2549:
2545:
2540:
2537:
2534:
2531:
2528:
2523:
2518:
2494:
2491:
2488:
2485:
2482:
2479:
2476:
2471:
2466:
2411:
2408:
2333:
2330:
2329:
2328:
2316:
2313:
2310:
2307:
2304:
2301:
2298:
2295:
2292:
2289:
2286:
2283:
2278:
2275:
2272:
2269:
2264:
2259:
2255:
2240:
2239:
2228:
2225:
2220:
2216:
2212:
2209:
2206:
2203:
2198:
2195:
2192:
2189:
2184:
2179:
2175:
2159:
2156:
2155:
2154:
2143:
2139:
2134:
2130:
2125:
2122:
2117:
2113:
2109:
2105:
2099:
2096:
2093:
2090:
2085:
2080:
2076:
2057:
2056:
2036:
2029:(, ), so (, )
2004:
2003:
1986:
1979:
1924:
1923:
1912:
1908:
1904:
1901:
1898:
1895:
1891:
1885:
1882:
1879:
1876:
1871:
1867:
1862:
1858:
1853:
1849:
1846:
1843:
1840:
1834:
1830:
1826:
1822:
1816:
1813:
1810:
1807:
1802:
1798:
1793:
1789:
1784:
1781:
1776:
1772:
1768:
1764:
1758:
1755:
1752:
1749:
1673:
1672:
1661:
1657:
1652:
1648:
1643:
1640:
1635:
1631:
1627:
1623:
1617:
1614:
1611:
1608:
1590:
1571:
1561:
1548:
1547:
1535:
1530:
1526:
1521:
1518:
1513:
1509:
1505:
1501:
1495:
1492:
1489:
1486:
1481:
1476:
1472:
1457:
1456:
1445:
1441:
1435:
1431:
1427:
1424:
1421:
1417:
1411:
1408:
1405:
1402:
1397:
1392:
1388:
1356:
1352:
1348:
1344:
1340:
1337:
1334:
1331:
1328:
1325:
1322:
1261:
1210:
1209:
1198:
1194:
1182:
1178:
1174:
1170:
1166:
1163:
1149:
1135:
1128:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1099:
1095:
1090:
1086:
1027:
1024:
1023:
1022:
1011:
1007:
1003:
1000:
997:
994:
990:
986:
959:
956:
953:
950:
947:
944:
941:
938:
935:
903:) is at least
890:
889:
878:
874:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
839:
833:
830:
827:
824:
821:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
784:
781:
778:
775:
772:
707:
704:
702:
699:
638:
637:Proof overview
635:
605:
601:
598:
587:Turing machine
573:
569:
565:
561:
558:
539:
536:
524:
523:
511:
508:
505:
502:
499:
496:
491:
488:
485:
482:
479:
474:
471:
468:
465:
462:
459:
456:
451:
448:
445:
442:
439:
367:
364:
361:
341:
336:
332:
328:
323:
320:
317:
314:
311:
306:
303:
298:
294:
290:
285:
282:
279:
276:
273:
213:
212:
200:
196:
193:
190:
187:
184:
181:
177:
174:
171:
168:
165:
160:
157:
154:
151:
148:
143:
139:
134:
130:
127:
124:
121:
117:
113:
109:
103:
100:
97:
94:
91:
15:
9:
6:
4:
3:
2:
3611:
3600:
3597:
3595:
3592:
3591:
3589:
3582:
3575:
3573:0-201-53082-1
3569:
3565:
3561:
3557:
3552:
3550:0-534-94728-X
3546:
3541:
3540:
3534:
3530:
3529:
3516:
3512:
3508:
3504:
3497:
3489:
3485:
3481:
3477:
3473:
3469:
3462:
3454:
3450:
3446:
3442:
3435:
3427:
3421:
3417:
3410:
3402:
3398:
3394:
3392:0-7695-2228-9
3388:
3384:
3380:
3376:
3369:
3360:
3355:
3351:
3347:
3343:
3336:
3328:
3324:
3320:
3316:
3311:
3306:
3302:
3298:
3294:
3290:
3286:
3279:
3270:
3265:
3261:
3257:
3251:
3243:
3239:
3235:
3231:
3226:
3221:
3217:
3213:
3209:
3205:
3198:
3190:
3186:
3182:
3178:
3174:
3170:
3165:
3160:
3156:
3152:
3151:
3146:
3142:
3138:
3137:Hartmanis, J.
3132:
3128:
3118:
3115:
3114:
3108:
3091:
3085:
3079:
3076:
3073:
3062:
3058:
3042:
3039:
3036:
3028:
3024:
3018:
3016:
3012:
3008:
3004:
3000:
2996:
2992:
2988:
2982:
2976:
2975:Neil D. Jones
2972:
2968:
2966:
2962:
2961:
2960:
2942:
2936:
2933:
2930:
2916:
2914:
2910:
2906:
2902:
2898:
2897:
2892:
2888:
2887:
2883:
2878:
2873:
2871:
2867:
2863:
2859:
2855:
2851:
2847:
2843:
2839:
2835:
2831:
2828:time but not
2827:
2823:
2819:
2815:
2811:
2807:
2802:
2783:
2780:
2776:
2750:
2746:
2741:
2735:
2732:
2726:
2723:
2719:
2713:
2709:
2705:
2682:
2678:
2673:
2669:
2665:
2600:
2592:
2589:
2585:
2559:
2551:
2547:
2521:
2469:
2455:For example,
2453:
2451:
2447:
2446:
2441:
2440:
2435:
2434:
2429:
2428:
2423:
2422:
2417:
2407:
2405:
2401:
2397:
2393:
2389:
2385:
2384:
2379:
2375:
2371:
2367:
2363:
2359:
2355:
2351:
2347:
2343:
2339:
2308:
2302:
2299:
2296:
2290:
2284:
2262:
2257:
2253:
2245:
2244:
2243:
2226:
2218:
2210:
2204:
2182:
2177:
2173:
2165:
2164:
2163:
2141:
2137:
2132:
2128:
2123:
2120:
2115:
2111:
2107:
2103:
2083:
2078:
2074:
2066:
2065:
2064:
2062:
2054:
2050:
2046:
2043:
2039:
2032:
2028:
2025:
2021:
2017:
2013:
2010:
2006:
2005:
2001:
1997:
1993:
1989:
1982:
1975:
1972:
1968:
1964:
1960:
1956:
1952:
1948:
1945:
1941:
1940:
1939:
1937:
1933:
1929:
1910:
1906:
1899:
1893:
1889:
1869:
1865:
1860:
1856:
1851:
1847:
1844:
1841:
1838:
1832:
1828:
1824:
1820:
1800:
1796:
1791:
1787:
1782:
1779:
1774:
1770:
1766:
1762:
1738:
1737:
1736:
1734:
1730:
1726:
1722:
1718:
1714:
1710:
1706:
1703:accepts. If
1702:
1698:
1694:
1690:
1686:
1682:
1678:
1659:
1655:
1650:
1646:
1641:
1638:
1633:
1629:
1625:
1621:
1597:
1596:
1595:
1593:
1586:
1582:
1578:
1574:
1566:
1564:
1557:
1553:
1533:
1528:
1524:
1519:
1516:
1511:
1507:
1503:
1499:
1479:
1474:
1470:
1462:
1461:
1460:
1443:
1439:
1433:
1425:
1419:
1415:
1395:
1390:
1386:
1378:
1377:
1376:
1374:
1370:
1346:
1338:
1332:
1326:
1320:
1312:
1308:
1304:
1300:
1296:
1292:
1288:
1284:
1280:
1276:
1272:
1268:
1264:
1256:
1254:
1250:
1246:
1242:
1238:
1233:
1231:
1227:
1223:
1219:
1215:
1196:
1192:
1172:
1161:
1147:
1133:
1116:
1113:
1107:
1097:
1093:
1088:
1084:
1076:
1075:
1074:
1071:
1069:
1065:
1061:
1057:
1053:
1049:
1045:
1041:
1037:
1033:
1009:
1005:
1001:
998:
995:
992:
988:
984:
977:
976:
975:
973:
957:
954:
951:
948:
945:
939:
933:
925:
922:but not time
921:
917:
913:
909:
906:
902:
898:
895:
876:
872:
865:
859:
856:
853:
847:
841:
837:
814:
802:
796:
790:
761:
760:
759:
757:
753:
749:
745:
741:
737:
733:
729:
725:
721:
717:
713:
698:
696:
692:
688:
684:
680:
676:
672:
668:
664:
660:
656:
652:
648:
644:
634:
632:
629:) steps. All
628:
624:
620:
599:
596:
588:
559:
556:
549:
545:
535:
533:
529:
503:
497:
472:
463:
457:
428:
427:
426:
424:
420:
416:
412:
408:
404:
400:
396:
392:
388:
384:
379:
365:
362:
359:
334:
330:
304:
296:
292:
260:
258:
254:
250:
246:
242:
238:
234:
230:
226:
222:
218:
191:
185:
182:
179:
172:
166:
141:
137:
132:
125:
119:
115:
111:
107:
80:
79:
78:
76:
72:
69:
65:
61:
57:
53:
49:
44:
42:
38:
35:time but not
34:
30:
26:
22:
3581:
3563:
3538:
3509:(1): 39β44.
3506:
3502:
3496:
3471:
3467:
3461:
3444:
3440:
3434:
3415:
3409:
3374:
3368:
3349:
3345:
3335:
3300:
3296:
3278:
3259:
3250:
3215:
3211:
3197:
3154:
3148:
3131:
3060:
3056:
3026:
3020:
3014:
3010:
3006:
3002:
2998:
2994:
2990:
2986:
2984:
2980:
2959:proved for:
2922:
2912:
2908:
2904:
2900:
2894:
2890:
2885:
2881:
2874:
2869:
2865:
2861:
2857:
2853:
2849:
2845:
2841:
2837:
2829:
2825:
2821:
2817:
2813:
2809:
2805:
2803:
2454:
2449:
2443:
2437:
2431:
2425:
2419:
2413:
2410:Consequences
2403:
2399:
2395:
2391:
2387:
2381:
2377:
2373:
2369:
2365:
2361:
2357:
2349:
2345:
2341:
2337:
2335:
2241:
2161:
2060:
2058:
2052:
2048:
2044:
2041:
2034:
2030:
2026:
2023:
2019:
2015:
2011:
2008:
1999:
1995:
1991:
1984:
1977:
1973:
1970:
1966:
1962:
1958:
1954:
1950:
1946:
1943:
1935:
1931:
1927:
1925:
1732:
1728:
1724:
1720:
1716:
1712:
1708:
1704:
1700:
1696:
1692:
1688:
1684:
1680:
1676:
1675:We use this
1674:
1588:
1584:
1580:
1576:
1569:
1567:
1559:
1555:
1551:
1549:
1458:
1372:
1368:
1310:
1306:
1302:
1298:
1294:
1290:
1286:
1282:
1278:
1274:
1270:
1266:
1259:
1257:
1252:
1248:
1244:
1240:
1236:
1234:
1229:
1225:
1221:
1217:
1213:
1211:
1072:
1067:
1063:
1059:
1055:
1051:
1047:
1043:
1039:
1035:
1031:
1029:
971:
923:
919:
915:
911:
910:
904:
900:
896:
893:
892:
755:
751:
747:
743:
739:
735:
731:
727:
719:
715:
711:
710:
693:)), using a
690:
686:
682:
674:
670:
666:
662:
658:
654:
650:
646:
642:
640:
626:
622:
618:
541:
525:
422:
418:
410:
406:
402:
398:
395:Albert Meyer
387:Stephen Cook
380:
261:
256:
252:
248:
240:
236:
224:
220:
214:
74:
70:
45:
40:
39:time, where
36:
32:
24:
18:
3474:: 602β611.
2047:accept in
2040:, and thus
1719:) is twice
1695:accepts if
1691:, and then
631:polynomials
3588:Categories
3123:References
2879:: whether
2638:. Indeed,
2436:β ... and
1232:|) steps.
538:Background
3470:matter".
3319:0004-5411
3234:0004-5411
3173:0002-9947
3080:ε
3037:ε
2934:
2751:⊊
2683:⊆
2601:⊆
2560:⊊
2522:⊆
2470:⊊
2300:
2263:∈
2183:∈
2158:Extension
2084:∉
1480:∉
1396:∈
1339:⋅
999:
955:
857:
815:⊊
758:)). Thus
706:Statement
600:∈
568:→
473:⊊
425:)), then
305:⊊
183:
142:⊊
3562:(1993).
3535:(1997).
3327:13561149
3111:See also
2913:NEXPTIME
2445:NEXPTIME
2129:⌋
2116:⌊
1857:⌋
1833:⌊
1788:⌋
1775:⌊
1647:⌋
1634:⌊
1587:) is in
1554:+ 1 for
1525:⌋
1512:⌊
970:, since
912:Example.
548:function
259:) time.
245:little o
3488:7527905
3401:5555450
3242:2347143
3189:0170805
3181:1994208
2909:EXPTIME
2905:EXPTIME
2452:β ....
2427:EXPTIME
2027:accepts
2012:rejects
1974:rejects
1947:accepts
1711:, then
1594:within
1141:accepts
974:is in
894:Note 1.
677:)), by
3570:
3547:
3486:
3422:
3399:
3389:
3325:
3317:
3297:J. ACM
3240:
3232:
3212:J. ACM
3187:
3179:
3171:
2901:PSPACE
2896:PSPACE
2862:DSPACE
2846:PSPACE
2507:since
2450:2-NEXP
2352:+1) =
1247:. Let
1235:Here,
1184:
1159:
1151:
1145:
1137:
1131:
1123:
532:advice
413:+1) =
393:, and
215:where
23:, the
3484:S2CID
3397:S2CID
3323:S2CID
3238:S2CID
3177:JSTOR
2907:, or
2850:DTIME
2814:DTIME
2433:2-EXP
2396:NTIME
2383:NTIME
1731:+ 1.
1188:steps
1044:DTIME
1032:DTIME
1026:Proof
750:)log
251:than
217:DTIME
3568:ISBN
3545:ISBN
3420:ISBN
3387:ISBN
3315:ISSN
3230:ISSN
3169:ISSN
3040:>
2911:and
2903:and
2893:and
2884:and
2872:)).
2406:)).
2045:does
1273:for
1062:)log
683:TIME
667:TIME
655:TIME
643:TIME
546:. A
363:<
249:less
54:and
3511:doi
3476:doi
3449:doi
3379:doi
3354:doi
3305:doi
3264:doi
3220:doi
3159:doi
3155:117
2985:If
2931:log
2336:If
2297:log
2033:in
2007:If
1942:If
1727:= 2
1568:If
1255:).
1070:).
996:log
952:log
918:log
854:log
714:If
180:log
77:),
19:In
3590::
3507:87
3505:.
3482:.
3468:do
3443:.
3395:.
3385:.
3350:26
3348:.
3344:.
3321:.
3313:.
3301:25
3299:.
3295:.
3287:;
3236:.
3228:.
3216:13
3214:.
3210:.
3185:MR
3183:.
3175:.
3167:.
3153:.
3147:.
3139:;
3107:.
3017:).
3003:af
2969:A
2899:,
2891:NP
2889:,
2886:NP
2844:β
2448:β
2442:β
2439:NP
2430:β
2424:β
2031:is
1733:N'
1285:(|
1228:(|
1155:in
1050:(2
697:.
534:.
3576:.
3553:.
3517:.
3513::
3490:.
3478::
3455:.
3451::
3445:5
3428:.
3403:.
3381::
3362:.
3356::
3329:.
3307::
3272:.
3266::
3244:.
3222::
3191:.
3161::
3095:)
3092:n
3089:(
3086:f
3083:)
3077:+
3074:1
3071:(
3061:n
3059:(
3057:f
3043:0
3027:f
3015:f
3011:a
3007:n
3005:(
2999:n
2997:(
2995:f
2991:n
2989:(
2987:f
2946:)
2943:n
2940:(
2937:f
2882:P
2870:n
2868:(
2866:f
2864:(
2858:n
2856:(
2854:f
2852:(
2842:P
2838:P
2830:n
2826:n
2822:k
2818:n
2816:(
2810:P
2806:P
2789:)
2784:n
2781:2
2777:2
2773:(
2768:E
2765:M
2762:I
2759:T
2756:D
2747:)
2742:)
2736:n
2733:2
2727:n
2724:2
2720:2
2714:(
2710:o
2706:(
2700:E
2697:M
2694:I
2691:T
2688:D
2679:)
2674:n
2670:2
2666:(
2660:E
2657:M
2654:I
2651:T
2648:D
2624:E
2621:M
2618:I
2615:T
2612:P
2609:X
2606:E
2598:)
2593:n
2590:2
2586:2
2582:(
2577:E
2574:M
2571:I
2568:T
2565:D
2557:)
2552:n
2548:2
2544:(
2539:E
2536:M
2533:I
2530:T
2527:D
2517:P
2493:E
2490:M
2487:I
2484:T
2481:P
2478:X
2475:E
2465:P
2421:P
2404:n
2402:(
2400:g
2398:(
2392:n
2390:(
2388:f
2386:(
2378:n
2376:(
2374:g
2370:n
2368:(
2366:f
2362:n
2360:(
2358:g
2356:(
2354:o
2350:n
2348:(
2346:f
2342:n
2340:(
2338:g
2327:.
2315:)
2312:)
2309:m
2306:(
2303:f
2294:)
2291:m
2288:(
2285:f
2282:(
2277:E
2274:M
2271:I
2268:T
2258:f
2254:H
2227:.
2224:)
2219:3
2215:)
2211:m
2208:(
2205:f
2202:(
2197:E
2194:M
2191:I
2188:T
2178:f
2174:H
2142:.
2138:)
2133:)
2124:2
2121:m
2112:(
2108:f
2104:(
2098:E
2095:M
2092:I
2089:T
2079:f
2075:H
2061:K
2053:n
2051:(
2049:f
2042:N
2037:f
2035:H
2024:K
2020:n
2018:(
2016:f
2009:N
2000:n
1998:(
1996:f
1992:N
1987:f
1985:H
1980:f
1978:H
1971:K
1967:n
1965:(
1963:f
1959:K
1955:n
1953:(
1951:f
1944:N
1936:N
1932:n
1928:N
1911:.
1907:)
1903:)
1900:n
1897:(
1894:f
1890:(
1884:E
1881:M
1878:I
1875:T
1870:=
1866:)
1861:)
1852:2
1848:1
1845:+
1842:n
1839:2
1829:(
1825:f
1821:(
1815:E
1812:M
1809:I
1806:T
1801:=
1797:)
1792:)
1783:2
1780:m
1771:(
1767:f
1763:(
1757:E
1754:M
1751:I
1748:T
1729:n
1725:m
1721:n
1717:K
1713:m
1709:N
1705:n
1701:K
1697:K
1693:N
1689:K
1685:K
1681:N
1677:K
1660:.
1656:)
1651:)
1642:2
1639:m
1630:(
1626:f
1622:(
1616:E
1613:M
1610:I
1607:T
1591:f
1589:H
1585:x
1581:x
1577:K
1572:f
1570:H
1562:f
1560:H
1556:m
1552:n
1534:)
1529:)
1520:2
1517:m
1508:(
1504:f
1500:(
1494:E
1491:M
1488:I
1485:T
1475:f
1471:H
1444:.
1440:)
1434:3
1430:)
1426:m
1423:(
1420:f
1416:(
1410:E
1407:M
1404:I
1401:T
1391:f
1387:H
1373:M
1369:M
1355:)
1351:|
1347:M
1343:|
1336:)
1333:n
1330:(
1327:T
1324:(
1321:O
1311:n
1309:(
1307:T
1303:m
1301:(
1299:f
1295:M
1291:M
1287:x
1283:f
1279:x
1277:(
1275:f
1271:M
1267:R
1262:f
1260:H
1253:x
1249:m
1245:M
1241:x
1237:M
1230:x
1226:f
1222:M
1218:x
1216:,
1214:M
1197:.
1193:}
1181:)
1177:|
1173:x
1169:|
1165:(
1162:f
1148:x
1134:M
1127:|
1120:)
1117:x
1114:,
1111:]
1108:M
1105:[
1102:(
1098:{
1094:=
1089:f
1085:H
1068:n
1066:(
1064:f
1060:n
1058:(
1056:f
1052:n
1048:f
1046:(
1040:n
1038:(
1036:f
1034:(
1010:.
1006:)
1002:n
993:n
989:(
985:o
972:n
958:n
949:n
946:=
943:)
940:n
937:(
934:f
924:n
920:n
916:n
905:n
901:n
899:(
897:f
877:.
873:)
869:)
866:n
863:(
860:f
851:)
848:n
845:(
842:f
838:(
832:E
829:M
826:I
823:T
820:D
812:)
809:)
806:)
803:n
800:(
797:f
794:(
791:o
788:(
783:E
780:M
777:I
774:T
771:D
756:n
754:(
752:f
748:n
746:(
744:f
742:(
740:O
736:n
734:(
732:f
730:(
728:o
720:n
718:(
716:f
691:n
689:(
687:g
685:(
675:n
673:(
671:f
669:(
663:n
661:(
659:f
657:(
651:n
649:(
647:g
645:(
627:n
625:(
623:f
619:n
604:N
597:n
572:N
564:N
560::
557:f
522:.
510:)
507:)
504:n
501:(
498:g
495:(
490:E
487:M
484:I
481:T
478:N
470:)
467:)
464:n
461:(
458:f
455:(
450:E
447:M
444:I
441:T
438:N
423:n
421:(
419:g
417:(
415:o
411:n
409:(
407:f
403:n
401:(
399:g
366:b
360:a
340:)
335:b
331:n
327:(
322:E
319:M
316:I
313:T
310:D
302:)
297:a
293:n
289:(
284:E
281:M
278:I
275:T
272:D
257:n
255:(
253:f
241:n
239:(
237:f
235:(
233:O
225:n
223:(
221:f
219:(
211:,
199:)
195:)
192:n
189:(
186:f
176:)
173:n
170:(
167:f
164:(
159:E
156:M
153:I
150:T
147:D
138:)
133:)
129:)
126:n
123:(
120:f
116:(
112:o
108:(
102:E
99:M
96:I
93:T
90:D
75:n
73:(
71:f
41:n
37:n
33:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.