188:
1294:
left-to-right order in which they are bound. After deciding a value for all quantified variables, the machine accepts if the resulting
Boolean formula evaluates to true, and rejects if it evaluates to false. Thus at an existentially quantified variable the machine is accepting if a value can be substituted for the variable that renders the remaining problem satisfiable, and at a universally quantified variable the machine is accepting if any value can be substituted and the remaining problem is satisfiable.
2217:
336:. An existential state is accepting if some transition leads to an accepting state; a universal state is accepting if every transition leads to an accepting state. (Thus a universal state with no transitions accepts unconditionally; an existential state with no transitions rejects unconditionally). The machine as a whole accepts if the initial state is accepting.
939:
When deciding if a configuration of an ATM is accepting or rejecting using the above definition, it is not always necessary to examine all configurations reachable from the current configuration. In particular, an existential configuration can be labelled as accepting if any successor configuration
1293:
in which each variable can be bound by either an existential or a universal quantifier. The alternating machine branches existentially to try all possible values of an existentially quantified variable and universally to try all possible values of a universally quantified variable, in the
1864:
879:
is said to be accepting when there exists some configuration reachable in one step that is accepting and rejecting when all configurations reachable in one step are rejecting (this is the type of all states in a classical NTM except the final state).
2092:
534:
1651:
1543:
1347:
The
Boolean satisfiability problem can be viewed as the special case where all variables are existentially quantified, allowing ordinary nondeterminism, which uses only existential branching, to solve it efficiently.
1962:
1442:
2737:
2394:
2589:
930:
Note that it is impossible for a configuration to be both accepting and rejecting, however, some configurations may be neither accepting or rejecting, due to the possibility of nonterminating computations.
665:
316:
choices lead to an accepting state does the whole computation accept. An alternating Turing machine (or to be more precise, the definition of acceptance for such a machine) alternates between these modes.
412:
1690:
1275:
1183:
2640:
3035:
2886:
2492:
844:
is said to be accepting if all configurations reachable in one step are accepting, and rejecting if some configuration reachable in one step is rejecting. A configuration with
3069:
2293:
sets. The states in even-numbered sets are universal and the states in odd-numbered sets are existential (or vice versa). The machine has no transitions between a state in set
2921:
2189:
2142:
2969:
1968:
3001:
842:
1218:
1103:
803:
749:
877:
577:
2830:
464:
457:
2420:
1129:
699:
1322:
921:
1065:
1036:
1007:
974:
2446:
1342:
435:
2774:. An alternating Turing machine, with one alternation, starting in an existential state, can solve this problem in polynomial time (by guessing a circuit
1550:
1449:
3159:
1870:
1366:
940:
is found to be accepting, and a universal configuration can be labelled as rejecting if any successor configuration is found to be rejecting.
2647:
2310:
1669:, considering the resources used by an ATM rather than a deterministic Turing machine. Chandra, Kozen, and Stockmeyer proved the theorems
2499:
2238:
584:
3360:
3334:
3311:
2840:
1286:
1009:
steps is sufficient to label the initial configuration as accepting or rejecting. An ATM decides a language in space
3279:
2264:
1859:{\displaystyle {\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})}
231:
209:
2246:
202:
2591:
is defined in the same way, but beginning in a universal state; it consists of the complements of the languages in
2285:
is an alternating Turing machine that switches from an existential to a universal state or vice versa no more than
354:
325:
257:
169:
2939:
alternations, starting in an existential (respectively, universal) state can decide all the problems in the class
245:
72:
3379:
2242:
1290:
1223:
1134:
2594:
2748:
87:
3006:
2846:
2455:
2195:
308:
choice leads to an accepting state, then the whole computation accepts. The definition of co-NP uses the
3192:
3040:
2087:{\displaystyle {\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),}
112:
97:
36:
2891:
2147:
2100:
3218:
2942:
3232:
2227:
196:
117:
107:
102:
92:
2974:
812:
264:) with a rule for accepting computations that generalizes the rules used in the definition of the
2231:
1188:
1073:
758:
704:
143:
82:
41:
847:
549:
529:{\displaystyle \delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})}
3322:
3227:
2782:
gates, then switching to a universal state, guessing an input, and checking that the output of
213:
77:
46:
3271:
2809:
442:
67:
3259:
2399:
1108:
678:
3072:
1300:
899:
162:
1041:
1012:
983:
950:
8:
2924:
2425:
3184:
3167:
1357:
1327:
420:
3356:
3330:
3307:
3275:
3260:
3188:
1351:
3237:
3176:
3135:
3127:
3104:
2843:, the logarithmic space hierarchy collapses to its first level. As a corollary the
2756:
280:
276:
265:
3210:
1646:{\displaystyle {\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})}
3350:
3267:
3079:
944:
268:
155:
3299:
1658:
22:
1538:{\displaystyle {\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})}
3373:
2289:−1 times. (It is an alternating Turing machine whose states are divided into
3255:
284:
122:
3180:
1285:
Perhaps the most natural problem for alternating machines to solve is the
3346:
3131:
1957:{\displaystyle {\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))}
927:) is accepting, and to reject if the initial configuration is rejecting.
138:
3108:
1437:{\displaystyle {\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})}
2732:{\displaystyle {\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)}
2422:
by a machine beginning in an existential state and alternating at most
3140:
2389:{\displaystyle {\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)}
1038:
if examining configurations that do not modify tape cells beyond the
3241:
2584:{\displaystyle {\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)}
2216:
1683:
3158:
Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981).
1352:
Complexity classes and comparison to deterministic Turing machines
1666:
923:, the head is at the left end of the tape, and the tape contains
3344:
3099:
Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "Alternation".
2194:
A more general form of these relationships is expressed by the
1662:
660:{\displaystyle g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}}
349:
272:
1297:
Such a machine decides quantified
Boolean formulas in time
3211:"Nondeterministic space is closed under complementation"
3124:
Proc. 17th IEEE Symp. on
Foundations of Computer Science
3101:
Proc. 17th IEEE Symp. on
Foundations of Computer Science
3122:
Kozen, D. (1976). "On parallelism in Turing machines".
2935:
An alternating Turing machine in polynomial time with
3321:
3157:
3043:
3009:
2977:
2945:
2894:
2849:
2812:
2650:
2597:
2502:
2458:
2428:
2402:
2313:
2150:
2103:
1971:
1873:
1693:
1553:
1452:
1369:
1330:
1303:
1226:
1191:
1137:
1111:
1076:
1044:
1015:
986:
953:
902:
850:
815:
761:
707:
681:
587:
552:
467:
445:
423:
357:
2739:
is defined similarly for space bounded computation.
287:in 1976, with a joint journal publication in 1981.
3063:
3029:
2995:
2963:
2915:
2880:
2824:
2731:
2634:
2583:
2486:
2440:
2414:
2388:
2183:
2136:
2086:
1956:
1858:
1645:
1537:
1436:
1336:
1316:
1269:
1212:
1177:
1123:
1097:
1059:
1030:
1001:
968:
915:
871:
836:
797:
743:
693:
659:
571:
528:
451:
429:
406:
3098:
3371:
3078:Another special case of time hierarchies is the
2766:, determine if there is a circuit with at most
1653:are the languages decidable in exponential time
1545:are the languages decidable in polynomial space
1070:A language that is decided by some ATM in time
3298:
1444:are the languages decidable in polynomial time
3153:
3151:
407:{\displaystyle M=(Q,\Gamma ,\delta ,q_{0},g)}
163:
3341:Section 16.2: Alternation, pp. 399–401.
3318:Section 10.3: Alternation, pp. 380–386.
2888:hierarchy collapses to its first level when
2396:is the class of languages decidable in time
654:
600:
520:
508:
2245:. Unsourced material may be challenged and
3148:
275:. The concept of an ATM was set forth by
170:
156:
3355:. Springer Science & Business Media.
3304:Introduction to the Theory of Computation
3231:
3139:
2265:Learn how and when to remove this message
232:Learn how and when to remove this message
3208:
1657:These are similar to the definitions of
1270:{\displaystyle {\mathsf {ASPACE}}(s(n))}
328:whose states are divided into two sets:
195:This article includes a list of general
3003:). These classes are sometimes denoted
1178:{\displaystyle {\mathsf {ATIME}}(t(n))}
295:
3372:
2864:
2861:
2858:
2855:
2852:
2770:gates that computes the same function
2715:
2712:
2709:
2706:
2703:
2668:
2665:
2662:
2659:
2656:
2653:
2635:{\displaystyle {\mathsf {ATIME}}(f,j)}
2612:
2609:
2606:
2603:
2600:
2567:
2564:
2561:
2558:
2523:
2520:
2517:
2514:
2511:
2508:
2505:
2470:
2467:
2464:
2461:
2372:
2369:
2366:
2363:
2328:
2325:
2322:
2319:
2316:
2201:
2045:
2042:
2039:
2036:
2033:
1989:
1986:
1983:
1980:
1977:
1974:
1931:
1928:
1925:
1922:
1919:
1916:
1888:
1885:
1882:
1879:
1876:
1817:
1814:
1811:
1808:
1805:
1767:
1764:
1761:
1758:
1755:
1711:
1708:
1705:
1702:
1699:
1696:
1615:
1612:
1609:
1606:
1603:
1577:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1514:
1511:
1508:
1505:
1502:
1499:
1473:
1470:
1467:
1464:
1461:
1458:
1455:
1413:
1410:
1407:
1404:
1401:
1375:
1372:
1244:
1241:
1238:
1235:
1232:
1229:
1152:
1149:
1146:
1143:
1140:
980:, examining configurations only up to
751:then that configuration is said to be
3254:
3121:
3092:
2793:
3352:Automata Theory and its Applications
3115:
3030:{\displaystyle \Sigma _{k}{\rm {P}}}
2881:{\displaystyle {\mathsf {SPACE}}(f)}
2786:on that input matches the output of
2243:adding citations to reliable sources
2210:
339:
181:
3103:. Houston, Texas. pp. 98–108.
2487:{\displaystyle {\mathsf {TIME}}(C)}
1289:, which is a generalization of the
536:is called the transition function (
13:
3292:
3126:. Houston, Texas. pp. 89–97.
3056:
3045:
3022:
3011:
2979:
2947:
2901:
2692:
2547:
2352:
1287:quantified Boolean formula problem
1185:, and a language decided in space
1067:cell from the left is sufficient.
934:
884:is said to accept an input string
502:
488:
480:
446:
373:
201:it lacks sufficient corresponding
14:
3391:
3064:{\displaystyle \Pi _{k}{\rm {P}}}
2832:of the hierarchy is in its level
3329:(1st ed.). Addison Wesley.
3306:(2nd ed.). PWS Publishing.
2930:
2916:{\displaystyle f=\Omega (\log )}
2279:alternating Turing machine with
2215:
2184:{\displaystyle g(n)\geq \log(n)}
2137:{\displaystyle f(n)\geq \log(n)}
888:if the initial configuration of
805:the configuration is said to be
667:specifies the type of each state
326:non-deterministic Turing machine
258:non-deterministic Turing machine
186:
2964:{\displaystyle \Sigma _{k}^{p}}
1360:are useful to define for ATMs:
246:computational complexity theory
73:Nondeterministic Turing machine
3248:
3202:
2910:
2904:
2875:
2869:
2726:
2720:
2685:
2673:
2629:
2617:
2578:
2572:
2540:
2528:
2481:
2475:
2383:
2377:
2345:
2333:
2178:
2172:
2160:
2154:
2131:
2125:
2113:
2107:
2078:
2069:
2062:
2050:
2009:
2006:
2000:
1994:
1951:
1948:
1942:
1936:
1908:
1905:
1899:
1893:
1853:
1848:
1845:
1839:
1833:
1822:
1797:
1792:
1786:
1772:
1731:
1728:
1722:
1716:
1640:
1620:
1532:
1519:
1431:
1418:
1291:Boolean satisfiability problem
1264:
1261:
1255:
1249:
1207:
1201:
1172:
1169:
1163:
1157:
1092:
1086:
1054:
1048:
1025:
1019:
996:
990:
963:
957:
860:
854:
825:
819:
771:
765:
717:
711:
597:
523:
493:
483:
401:
364:
300:The definition of NP uses the
290:
1:
3085:
2841:Immerman–Szelepcsényi theorem
2206:
2996:{\displaystyle \Pi _{k}^{p}}
2798:It is said that a hierarchy
2749:circuit minimization problem
2742:
837:{\displaystyle g(q)=\wedge }
88:Probabilistic Turing machine
7:
2806:if every language in level
2196:parallel computation thesis
1220:is said to be in the class
1213:{\displaystyle c\cdot s(n)}
1131:is said to be in the class
1098:{\displaystyle c\cdot t(n)}
976:if, on any input of length
798:{\displaystyle g(q)=reject}
744:{\displaystyle g(q)=accept}
459:is the finite tape alphabet
437:is the finite set of states
10:
3396:
1280:
872:{\displaystyle g(q)=\vee }
572:{\displaystyle q_{0}\in Q}
346:alternating Turing machine
322:alternating Turing machine
250:alternating Turing machine
113:Unambiguous Turing machine
98:Multi-track Turing machine
63:Alternating Turing machine
37:Turing machine equivalents
16:Abstract computation model
3219:SIAM Journal on Computing
540:shifts the head left and
3327:Computational Complexity
3071:, respectively. See the
2448:times. It is called the
809:. A configuration with
312:of computation: only if
118:Universal Turing machine
103:Symmetric Turing machine
93:Multitape Turing machine
3209:Immerman, Neil (1988).
2825:{\displaystyle k\geq j}
452:{\displaystyle \Gamma }
344:Formally, a (one-tape)
216:more precise citations.
144:Category:Turing machine
42:Turing machine examples
3345:Bakhadyr Khoussainov;
3323:Christos Papadimitriou
3065:
3031:
2997:
2965:
2917:
2882:
2839:As a corollary of the
2826:
2733:
2636:
2585:
2488:
2442:
2416:
2415:{\displaystyle f\in C}
2390:
2185:
2138:
2088:
1958:
1860:
1647:
1539:
1438:
1338:
1318:
1271:
1214:
1179:
1125:
1124:{\displaystyle c>0}
1099:
1061:
1032:
1003:
970:
917:
873:
838:
799:
745:
695:
694:{\displaystyle q\in Q}
661:
573:
544:shifts the head right)
530:
453:
431:
408:
78:Quantum Turing machine
47:Turing machine gallery
3380:Models of computation
3262:Theory of Computation
3181:10.1145/322234.322243
3080:logarithmic hierarchy
3075:article for details.
3066:
3032:
2998:
2966:
2918:
2883:
2827:
2734:
2637:
2586:
2489:
2443:
2417:
2391:
2186:
2139:
2089:
1959:
1861:
1648:
1540:
1439:
1339:
1319:
1317:{\displaystyle n^{2}}
1272:
1215:
1180:
1126:
1100:
1062:
1033:
1004:
971:
918:
916:{\displaystyle q_{0}}
874:
839:
800:
746:
696:
662:
574:
531:
454:
432:
409:
283:and independently by
68:Neural Turing machine
3132:10.1109/SFCS.1976.20
3073:polynomial hierarchy
3041:
3007:
2975:
2943:
2892:
2847:
2810:
2648:
2595:
2500:
2456:
2426:
2400:
2311:
2239:improve this section
2148:
2101:
1969:
1871:
1691:
1551:
1450:
1367:
1328:
1301:
1224:
1189:
1135:
1109:
1074:
1060:{\displaystyle s(n)}
1042:
1031:{\displaystyle s(n)}
1013:
1002:{\displaystyle t(n)}
984:
969:{\displaystyle t(n)}
951:
900:
848:
813:
759:
705:
679:
585:
579:is the initial state
550:
465:
443:
421:
355:
296:Informal description
108:Total Turing machine
3109:10.1109/SFCS.1976.4
2992:
2960:
2925:space constructible
2441:{\displaystyle j-1}
2297:and a state in set
2202:Bounded alternation
304:of computation: if
83:Post–Turing machine
3198:on April 12, 2016.
3168:Journal of the ACM
3061:
3027:
2993:
2978:
2961:
2946:
2913:
2878:
2822:
2794:Collapsing classes
2751:: given a circuit
2729:
2632:
2581:
2484:
2438:
2412:
2386:
2181:
2134:
2084:
2030:
1954:
1856:
1752:
1643:
1600:
1535:
1496:
1434:
1398:
1358:complexity classes
1334:
1314:
1267:
1210:
1175:
1121:
1105:for some constant
1095:
1057:
1028:
999:
966:
913:
869:
834:
795:
741:
691:
657:
569:
526:
449:
427:
404:
330:existential states
266:complexity classes
3362:978-1-4612-0171-7
3336:978-0-201-53082-7
3313:978-0-534-95097-2
2275:
2274:
2267:
2015:
1737:
1679:APSPACE = EXPTIME
1585:
1481:
1383:
1337:{\displaystyle n}
943:An ATM decides a
430:{\displaystyle Q}
340:Formal definition
242:
241:
234:
180:
179:
3387:
3366:
3340:
3317:
3286:
3285:
3265:
3252:
3246:
3245:
3235:
3215:
3206:
3200:
3199:
3197:
3191:. Archived from
3164:
3155:
3146:
3145:
3143:
3119:
3113:
3112:
3096:
3070:
3068:
3067:
3062:
3060:
3059:
3053:
3052:
3036:
3034:
3033:
3028:
3026:
3025:
3019:
3018:
3002:
3000:
2999:
2994:
2991:
2986:
2970:
2968:
2967:
2962:
2959:
2954:
2922:
2920:
2919:
2914:
2887:
2885:
2884:
2879:
2868:
2867:
2835:
2831:
2829:
2828:
2823:
2805:
2790:on that input).
2757:Boolean function
2738:
2736:
2735:
2730:
2719:
2718:
2700:
2699:
2672:
2671:
2641:
2639:
2638:
2633:
2616:
2615:
2590:
2588:
2587:
2582:
2571:
2570:
2555:
2554:
2527:
2526:
2493:
2491:
2490:
2485:
2474:
2473:
2452:th level of the
2451:
2447:
2445:
2444:
2439:
2421:
2419:
2418:
2413:
2395:
2393:
2392:
2387:
2376:
2375:
2360:
2359:
2332:
2331:
2270:
2263:
2259:
2256:
2250:
2219:
2211:
2190:
2188:
2187:
2182:
2143:
2141:
2140:
2135:
2093:
2091:
2090:
2085:
2077:
2076:
2049:
2048:
2029:
1993:
1992:
1963:
1961:
1960:
1955:
1935:
1934:
1892:
1891:
1865:
1863:
1862:
1857:
1852:
1851:
1821:
1820:
1796:
1795:
1771:
1770:
1751:
1715:
1714:
1652:
1650:
1649:
1644:
1639:
1638:
1637:
1636:
1619:
1618:
1599:
1581:
1580:
1544:
1542:
1541:
1536:
1531:
1530:
1518:
1517:
1495:
1477:
1476:
1443:
1441:
1440:
1435:
1430:
1429:
1417:
1416:
1397:
1379:
1378:
1343:
1341:
1340:
1335:
1323:
1321:
1320:
1315:
1313:
1312:
1276:
1274:
1273:
1268:
1248:
1247:
1219:
1217:
1216:
1211:
1184:
1182:
1181:
1176:
1156:
1155:
1130:
1128:
1127:
1122:
1104:
1102:
1101:
1096:
1066:
1064:
1063:
1058:
1037:
1035:
1034:
1029:
1008:
1006:
1005:
1000:
979:
975:
973:
972:
967:
922:
920:
919:
914:
912:
911:
878:
876:
875:
870:
843:
841:
840:
835:
804:
802:
801:
796:
750:
748:
747:
742:
700:
698:
697:
692:
666:
664:
663:
658:
578:
576:
575:
570:
562:
561:
535:
533:
532:
527:
492:
491:
458:
456:
455:
450:
436:
434:
433:
428:
413:
411:
410:
405:
394:
393:
334:universal states
302:existential mode
237:
230:
226:
223:
217:
212:this article by
203:inline citations
190:
189:
182:
172:
165:
158:
19:
18:
3395:
3394:
3390:
3389:
3388:
3386:
3385:
3384:
3370:
3369:
3363:
3337:
3314:
3295:
3293:Further reading
3290:
3289:
3282:
3268:Springer-Verlag
3253:
3249:
3242:10.1137/0217058
3213:
3207:
3203:
3195:
3162:
3156:
3149:
3120:
3116:
3097:
3093:
3088:
3055:
3054:
3048:
3044:
3042:
3039:
3038:
3021:
3020:
3014:
3010:
3008:
3005:
3004:
2987:
2982:
2976:
2973:
2972:
2971:(respectively,
2955:
2950:
2944:
2941:
2940:
2933:
2893:
2890:
2889:
2851:
2850:
2848:
2845:
2844:
2833:
2811:
2808:
2807:
2803:
2796:
2745:
2702:
2701:
2695:
2691:
2652:
2651:
2649:
2646:
2645:
2599:
2598:
2596:
2593:
2592:
2557:
2556:
2550:
2546:
2504:
2503:
2501:
2498:
2497:
2460:
2459:
2457:
2454:
2453:
2449:
2427:
2424:
2423:
2401:
2398:
2397:
2362:
2361:
2355:
2351:
2315:
2314:
2312:
2309:
2308:
2271:
2260:
2254:
2251:
2236:
2220:
2209:
2204:
2149:
2146:
2145:
2102:
2099:
2098:
2072:
2068:
2032:
2031:
2019:
1973:
1972:
1970:
1967:
1966:
1915:
1914:
1875:
1874:
1872:
1869:
1868:
1829:
1825:
1804:
1803:
1779:
1775:
1754:
1753:
1741:
1695:
1694:
1692:
1689:
1688:
1632:
1628:
1627:
1623:
1602:
1601:
1589:
1555:
1554:
1552:
1549:
1548:
1526:
1522:
1498:
1497:
1485:
1454:
1453:
1451:
1448:
1447:
1425:
1421:
1400:
1399:
1387:
1371:
1370:
1368:
1365:
1364:
1354:
1329:
1326:
1325:
1308:
1304:
1302:
1299:
1298:
1283:
1228:
1227:
1225:
1222:
1221:
1190:
1187:
1186:
1139:
1138:
1136:
1133:
1132:
1110:
1107:
1106:
1075:
1072:
1071:
1043:
1040:
1039:
1014:
1011:
1010:
985:
982:
981:
977:
952:
949:
948:
945:formal language
937:
935:Resource bounds
907:
903:
901:
898:
897:
849:
846:
845:
814:
811:
810:
760:
757:
756:
706:
703:
702:
680:
677:
676:
586:
583:
582:
557:
553:
551:
548:
547:
487:
486:
466:
463:
462:
444:
441:
440:
422:
419:
418:
389:
385:
356:
353:
352:
342:
298:
293:
238:
227:
221:
218:
208:Please help to
207:
191:
187:
176:
23:Turing machines
17:
12:
11:
5:
3393:
3383:
3382:
3368:
3367:
3361:
3342:
3335:
3319:
3312:
3300:Michael Sipser
3294:
3291:
3288:
3287:
3280:
3247:
3233:10.1.1.54.5941
3226:(5): 935–938.
3201:
3175:(1): 114–133.
3147:
3114:
3090:
3089:
3087:
3084:
3058:
3051:
3047:
3024:
3017:
3013:
2990:
2985:
2981:
2958:
2953:
2949:
2932:
2929:
2912:
2909:
2906:
2903:
2900:
2897:
2877:
2874:
2871:
2866:
2863:
2860:
2857:
2854:
2821:
2818:
2815:
2795:
2792:
2744:
2741:
2728:
2725:
2722:
2717:
2714:
2711:
2708:
2705:
2698:
2694:
2690:
2687:
2684:
2681:
2678:
2675:
2670:
2667:
2664:
2661:
2658:
2655:
2631:
2628:
2625:
2622:
2619:
2614:
2611:
2608:
2605:
2602:
2580:
2577:
2574:
2569:
2566:
2563:
2560:
2553:
2549:
2545:
2542:
2539:
2536:
2533:
2530:
2525:
2522:
2519:
2516:
2513:
2510:
2507:
2483:
2480:
2477:
2472:
2469:
2466:
2463:
2437:
2434:
2431:
2411:
2408:
2405:
2385:
2382:
2379:
2374:
2371:
2368:
2365:
2358:
2354:
2350:
2347:
2344:
2341:
2338:
2335:
2330:
2327:
2324:
2321:
2318:
2273:
2272:
2223:
2221:
2214:
2208:
2205:
2203:
2200:
2180:
2177:
2174:
2171:
2168:
2165:
2162:
2159:
2156:
2153:
2133:
2130:
2127:
2124:
2121:
2118:
2115:
2112:
2109:
2106:
2095:
2094:
2083:
2080:
2075:
2071:
2067:
2064:
2061:
2058:
2055:
2052:
2047:
2044:
2041:
2038:
2035:
2028:
2025:
2022:
2018:
2014:
2011:
2008:
2005:
2002:
1999:
1996:
1991:
1988:
1985:
1982:
1979:
1976:
1964:
1953:
1950:
1947:
1944:
1941:
1938:
1933:
1930:
1927:
1924:
1921:
1918:
1913:
1910:
1907:
1904:
1901:
1898:
1895:
1890:
1887:
1884:
1881:
1878:
1866:
1855:
1850:
1847:
1844:
1841:
1838:
1835:
1832:
1828:
1824:
1819:
1816:
1813:
1810:
1807:
1802:
1799:
1794:
1791:
1788:
1785:
1782:
1778:
1774:
1769:
1766:
1763:
1760:
1757:
1750:
1747:
1744:
1740:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1713:
1710:
1707:
1704:
1701:
1698:
1686:
1680:
1677:
1674:
1655:
1654:
1642:
1635:
1631:
1626:
1622:
1617:
1614:
1611:
1608:
1605:
1598:
1595:
1592:
1588:
1584:
1579:
1576:
1573:
1570:
1567:
1564:
1561:
1558:
1546:
1534:
1529:
1525:
1521:
1516:
1513:
1510:
1507:
1504:
1501:
1494:
1491:
1488:
1484:
1480:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1445:
1433:
1428:
1424:
1420:
1415:
1412:
1409:
1406:
1403:
1396:
1393:
1390:
1386:
1382:
1377:
1374:
1356:The following
1353:
1350:
1333:
1311:
1307:
1282:
1279:
1266:
1263:
1260:
1257:
1254:
1251:
1246:
1243:
1240:
1237:
1234:
1231:
1209:
1206:
1203:
1200:
1197:
1194:
1174:
1171:
1168:
1165:
1162:
1159:
1154:
1151:
1148:
1145:
1142:
1120:
1117:
1114:
1094:
1091:
1088:
1085:
1082:
1079:
1056:
1053:
1050:
1047:
1027:
1024:
1021:
1018:
998:
995:
992:
989:
965:
962:
959:
956:
936:
933:
910:
906:
892:(the state of
868:
865:
862:
859:
856:
853:
833:
830:
827:
824:
821:
818:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
690:
687:
684:
675:is in a state
669:
668:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
608:
605:
602:
599:
596:
593:
590:
580:
568:
565:
560:
556:
545:
525:
522:
519:
516:
513:
510:
507:
504:
501:
498:
495:
490:
485:
482:
479:
476:
473:
470:
460:
448:
438:
426:
403:
400:
397:
392:
388:
384:
381:
378:
375:
372:
369:
366:
363:
360:
341:
338:
310:universal mode
297:
294:
292:
289:
240:
239:
194:
192:
185:
178:
177:
175:
174:
167:
160:
152:
149:
148:
147:
146:
141:
133:
132:
128:
127:
126:
125:
120:
115:
110:
105:
100:
95:
90:
85:
80:
75:
70:
65:
57:
56:
52:
51:
50:
49:
44:
39:
31:
30:
26:
25:
15:
9:
6:
4:
3:
2:
3392:
3381:
3378:
3377:
3375:
3364:
3358:
3354:
3353:
3348:
3343:
3338:
3332:
3328:
3324:
3320:
3315:
3309:
3305:
3301:
3297:
3296:
3283:
3281:9781846282973
3277:
3273:
3269:
3264:
3263:
3257:
3256:Kozen, Dexter
3251:
3243:
3239:
3234:
3229:
3225:
3221:
3220:
3212:
3205:
3194:
3190:
3186:
3182:
3178:
3174:
3170:
3169:
3161:
3160:"Alternation"
3154:
3152:
3142:
3137:
3133:
3129:
3125:
3118:
3110:
3106:
3102:
3095:
3091:
3083:
3081:
3076:
3074:
3049:
3015:
2988:
2983:
2956:
2951:
2938:
2931:Special cases
2928:
2926:
2907:
2898:
2895:
2872:
2842:
2837:
2819:
2816:
2813:
2801:
2791:
2789:
2785:
2781:
2778:with at most
2777:
2773:
2769:
2765:
2762:and a number
2761:
2758:
2754:
2750:
2747:Consider the
2740:
2723:
2696:
2688:
2682:
2679:
2676:
2643:
2626:
2623:
2620:
2575:
2551:
2543:
2537:
2534:
2531:
2495:
2478:
2435:
2432:
2429:
2409:
2406:
2403:
2380:
2356:
2348:
2342:
2339:
2336:
2306:
2304:
2300:
2296:
2292:
2288:
2284:
2282:
2269:
2266:
2258:
2248:
2244:
2240:
2234:
2233:
2229:
2224:This section
2222:
2218:
2213:
2212:
2199:
2197:
2192:
2175:
2169:
2166:
2163:
2157:
2151:
2128:
2122:
2119:
2116:
2110:
2104:
2081:
2073:
2065:
2059:
2056:
2053:
2026:
2023:
2020:
2016:
2012:
2003:
1997:
1965:
1945:
1939:
1911:
1902:
1896:
1867:
1842:
1836:
1830:
1826:
1800:
1789:
1783:
1780:
1776:
1748:
1745:
1742:
1738:
1734:
1725:
1719:
1687:
1685:
1681:
1678:
1675:
1673:ALOGSPACE = P
1672:
1671:
1670:
1668:
1664:
1660:
1633:
1629:
1624:
1596:
1593:
1590:
1586:
1582:
1547:
1527:
1523:
1492:
1489:
1486:
1482:
1478:
1446:
1426:
1422:
1394:
1391:
1388:
1384:
1380:
1363:
1362:
1361:
1359:
1349:
1345:
1331:
1309:
1305:
1295:
1292:
1288:
1278:
1258:
1252:
1204:
1198:
1195:
1192:
1166:
1160:
1118:
1115:
1112:
1089:
1083:
1080:
1077:
1068:
1051:
1045:
1022:
1016:
993:
987:
960:
954:
946:
941:
932:
928:
926:
908:
904:
895:
891:
887:
883:
866:
863:
857:
851:
831:
828:
822:
816:
808:
792:
789:
786:
783:
780:
777:
774:
768:
762:
754:
738:
735:
732:
729:
726:
723:
720:
714:
708:
688:
685:
682:
674:
651:
648:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
615:
612:
609:
606:
603:
594:
591:
588:
581:
566:
563:
558:
554:
546:
543:
539:
517:
514:
511:
505:
499:
496:
477:
474:
471:
468:
461:
439:
424:
417:
416:
415:
398:
395:
390:
386:
382:
379:
376:
370:
367:
361:
358:
351:
347:
337:
335:
331:
327:
323:
318:
315:
311:
307:
303:
288:
286:
282:
278:
274:
270:
267:
263:
259:
255:
251:
247:
236:
233:
225:
215:
211:
205:
204:
198:
193:
184:
183:
173:
168:
166:
161:
159:
154:
153:
151:
150:
145:
142:
140:
137:
136:
135:
134:
130:
129:
124:
121:
119:
116:
114:
111:
109:
106:
104:
101:
99:
96:
94:
91:
89:
86:
84:
81:
79:
76:
74:
71:
69:
66:
64:
61:
60:
59:
58:
54:
53:
48:
45:
43:
40:
38:
35:
34:
33:
32:
28:
27:
24:
21:
20:
3351:
3326:
3303:
3261:
3250:
3223:
3217:
3204:
3193:the original
3172:
3166:
3123:
3117:
3100:
3094:
3077:
2936:
2934:
2838:
2799:
2797:
2787:
2783:
2779:
2775:
2771:
2767:
2763:
2759:
2755:computing a
2752:
2746:
2644:
2496:
2307:
2302:
2298:
2294:
2290:
2286:
2283:alternations
2280:
2278:
2276:
2261:
2255:October 2013
2252:
2237:Please help
2225:
2193:
2096:
1656:
1355:
1346:
1296:
1284:
1069:
942:
938:
929:
924:
893:
889:
885:
881:
806:
752:
672:
670:
541:
537:
345:
343:
333:
329:
321:
319:
313:
309:
305:
301:
299:
261:
253:
249:
243:
228:
219:
200:
123:Zeno machine
62:
3347:Anil Nerode
2494:hierarchy.
1682:AEXPTIME =
1676:AP = PSPACE
291:Definitions
214:introducing
139:Alan Turing
3270:. p.
3086:References
2207:Definition
1324:and space
281:Stockmeyer
197:references
3228:CiteSeerX
3189:238863413
3141:1813/7056
3046:Π
3012:Σ
2980:Π
2948:Σ
2902:Ω
2817:≥
2802:to level
2800:collapses
2693:Σ
2548:Π
2433:−
2407:∈
2353:Σ
2226:does not
2170:
2164:≥
2123:
2117:≥
2057:×
2017:⋃
2013:⊆
1912:⊆
1739:⋃
1587:⋃
1483:⋃
1385:⋃
1196:⋅
1081:⋅
867:∨
832:∧
807:rejecting
755:, and if
753:accepting
686:∈
610:∨
604:∧
598:→
564:∈
506:×
503:Γ
500:×
484:→
481:Γ
478:×
469:δ
447:Γ
380:δ
374:Γ
3374:Category
3349:(2012).
3325:(1993).
3302:(2006).
3258:(2006).
1684:EXPSPACE
947:in time
222:May 2011
55:Variants
2743:Example
2247:removed
2232:sources
1667:EXPTIME
1281:Example
348:is a 5-
277:Chandra
256:) is a
210:improve
131:Science
29:Machine
3359:
3333:
3310:
3278:
3230:
3187:
1665:, and
1663:PSPACE
414:where
199:, but
3214:(PDF)
3196:(PDF)
3185:S2CID
3163:(PDF)
2301:<
2097:when
701:with
350:tuple
324:is a
285:Kozen
273:co-NP
248:, an
3357:ISBN
3331:ISBN
3308:ISBN
3276:ISBN
3037:and
2230:any
2228:cite
2144:and
2024:>
1746:>
1594:>
1490:>
1392:>
1116:>
332:and
279:and
271:and
3238:doi
3177:doi
3136:hdl
3128:doi
3105:doi
2923:is
2908:log
2305:.)
2277:An
2241:by
2167:log
2120:log
896:is
671:If
320:An
314:all
306:any
262:NTM
254:ATM
244:In
3376::
3274:.
3272:58
3266:.
3236:.
3224:17
3222:.
3216:.
3183:.
3173:28
3171:.
3165:.
3150:^
3134:.
3082:.
2927:.
2836:.
2642:.
2198:.
2191:.
1661:,
1344:.
1277:.
269:NP
3365:.
3339:.
3316:.
3284:.
3244:.
3240::
3179::
3144:.
3138::
3130::
3111:.
3107::
3057:P
3050:k
3023:P
3016:k
2989:p
2984:k
2957:p
2952:k
2937:k
2911:)
2905:(
2899:=
2896:f
2876:)
2873:f
2870:(
2865:E
2862:C
2859:A
2856:P
2853:S
2834:j
2820:j
2814:k
2804:j
2788:A
2784:B
2780:n
2776:B
2772:f
2768:n
2764:n
2760:f
2753:A
2727:)
2724:C
2721:(
2716:E
2713:C
2710:A
2707:P
2704:S
2697:j
2689:=
2686:)
2683:j
2680:,
2677:C
2674:(
2669:E
2666:C
2663:A
2660:P
2657:S
2654:A
2630:)
2627:j
2624:,
2621:f
2618:(
2613:E
2610:M
2607:I
2604:T
2601:A
2579:)
2576:C
2573:(
2568:E
2565:M
2562:I
2559:T
2552:j
2544:=
2541:)
2538:j
2535:,
2532:C
2529:(
2524:E
2521:M
2518:I
2515:T
2512:A
2509:o
2506:c
2482:)
2479:C
2476:(
2471:E
2468:M
2465:I
2462:T
2450:j
2436:1
2430:j
2410:C
2404:f
2384:)
2381:C
2378:(
2373:E
2370:M
2367:I
2364:T
2357:j
2349:=
2346:)
2343:j
2340:,
2337:C
2334:(
2329:E
2326:M
2323:I
2320:T
2317:A
2303:i
2299:j
2295:i
2291:k
2287:k
2281:k
2268:)
2262:(
2257:)
2253:(
2249:.
2235:.
2179:)
2176:n
2173:(
2161:)
2158:n
2155:(
2152:g
2132:)
2129:n
2126:(
2114:)
2111:n
2108:(
2105:f
2082:,
2079:)
2074:2
2070:)
2066:n
2063:(
2060:g
2054:c
2051:(
2046:E
2043:M
2040:I
2037:T
2034:A
2027:0
2021:c
2010:)
2007:)
2004:n
2001:(
1998:g
1995:(
1990:E
1987:C
1984:A
1981:P
1978:S
1975:N
1952:)
1949:)
1946:n
1943:(
1940:g
1937:(
1932:E
1929:C
1926:A
1923:P
1920:S
1917:D
1909:)
1906:)
1903:n
1900:(
1897:g
1894:(
1889:E
1886:M
1883:I
1880:T
1877:A
1854:)
1849:)
1846:)
1843:n
1840:(
1837:f
1834:(
1831:O
1827:2
1823:(
1818:E
1815:M
1812:I
1809:T
1806:D
1801:=
1798:)
1793:)
1790:n
1787:(
1784:f
1781:c
1777:2
1773:(
1768:E
1765:M
1762:I
1759:T
1756:D
1749:0
1743:c
1735:=
1732:)
1729:)
1726:n
1723:(
1720:f
1717:(
1712:E
1709:C
1706:A
1703:P
1700:S
1697:A
1659:P
1641:)
1634:k
1630:n
1625:2
1621:(
1616:E
1613:M
1610:I
1607:T
1604:A
1597:0
1591:k
1583:=
1578:E
1575:M
1572:I
1569:T
1566:P
1563:X
1560:E
1557:A
1533:)
1528:k
1524:n
1520:(
1515:E
1512:C
1509:A
1506:P
1503:S
1500:A
1493:0
1487:k
1479:=
1474:E
1471:C
1468:A
1465:P
1462:S
1459:P
1456:A
1432:)
1427:k
1423:n
1419:(
1414:E
1411:M
1408:I
1405:T
1402:A
1395:0
1389:k
1381:=
1376:P
1373:A
1332:n
1310:2
1306:n
1265:)
1262:)
1259:n
1256:(
1253:s
1250:(
1245:E
1242:C
1239:A
1236:P
1233:S
1230:A
1208:)
1205:n
1202:(
1199:s
1193:c
1173:)
1170:)
1167:n
1164:(
1161:t
1158:(
1153:E
1150:M
1147:I
1144:T
1141:A
1119:0
1113:c
1093:)
1090:n
1087:(
1084:t
1078:c
1055:)
1052:n
1049:(
1046:s
1026:)
1023:n
1020:(
1017:s
997:)
994:n
991:(
988:t
978:n
964:)
961:n
958:(
955:t
925:w
909:0
905:q
894:M
890:M
886:w
882:M
864:=
861:)
858:q
855:(
852:g
829:=
826:)
823:q
820:(
817:g
793:t
790:c
787:e
784:j
781:e
778:r
775:=
772:)
769:q
766:(
763:g
739:t
736:p
733:e
730:c
727:c
724:a
721:=
718:)
715:q
712:(
709:g
689:Q
683:q
673:M
655:}
652:t
649:c
646:e
643:j
640:e
637:r
634:,
631:t
628:p
625:e
622:c
619:c
616:a
613:,
607:,
601:{
595:Q
592::
589:g
567:Q
559:0
555:q
542:R
538:L
524:)
521:}
518:R
515:,
512:L
509:{
497:Q
494:(
489:P
475:Q
472::
425:Q
402:)
399:g
396:,
391:0
387:q
383:,
377:,
371:,
368:Q
365:(
362:=
359:M
260:(
252:(
235:)
229:(
224:)
220:(
206:.
171:e
164:t
157:v
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.