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