367:
Generalizations of many fully observable games are EXPTIME-complete. These games can be viewed as particular instances of a class of transition systems defined in terms of a set of state variables and actions/events that change the values of the state variables, together with the question of whether
198:
249:
2-EXPTIME is one class in a hierarchy of complexity classes with increasingly higher time bounds. The class 3-EXPTIME is defined similarly to 2-EXPTIME but with a triply exponential time bound
76:
295:
246:
in exponential space. This is one way to see that EXPSPACE ⊆ 2-EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.
320:
over a field. In the worst case, a Gröbner basis may have a number of elements which is doubly exponential in the number of variables. On the other hand, the
540:
660:
438:
561:
415:
345:
193:{\displaystyle {\mathsf {2{\mbox{-}}EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{2^{n^{k}}}\right).}
488:
Kapur, Deepak; Narendran, Paliath (1992), "Double-exponential complexity of computing a complete set of AC-unifiers",
1022:
507:
653:
17:
531:
Johannsen, Jan; Lange, Martin (2003), "CTL is complete for double exponential time", in Baeten, Jos C. M.;
40:
324:
of Gröbner basis algorithms is doubly exponential in the number of variables as well as in the entry size.
1057:
646:
389:
373:
1038:
845:
622:
567:
252:
243:
242:
2-EXPTIME can also be reformulated as the space class AEXPSPACE, the problems that can be solved by an
461:
600:
Proceedings of the 35th
International Colloquium on Automata, Languages and Programming (ICALP 2008)
542:
Proceedings of the 30th
International Colloquium on Automata, Languages and Programming (ICALP 2003)
1027:
352:
435:
981:
407:
337:
331:
976:
971:
321:
310:
491:[1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science
966:
536:
8:
56:
548:, Lecture Notes in Computer Science, vol. 2719, Springer-Verlag, pp. 767–775,
513:
459:
Dubé, Thomas W. (August 1990). "The
Structure of Polynomial Ideals and Gröbner Bases".
427:
356:
986:
557:
532:
517:
503:
411:
341:
32:
950:
840:
772:
762:
669:
603:
549:
495:
470:
431:
369:
36:
21:
317:
945:
935:
892:
882:
875:
865:
855:
813:
808:
803:
787:
767:
745:
740:
735:
723:
718:
713:
708:
592:
442:
211:
607:
940:
828:
750:
703:
207:
44:
1051:
553:
499:
630:
Proceedings of
International Conference on Automated Planning and Scheduling
489:
818:
728:
930:
755:
372:
exists. A generalization of this class of fully observable problems to
235:
638:
593:"Finite Automata, Digraph Connectivity, and Regular Expression Size"
474:
920:
915:
860:
683:
447:
Proceedings of the SIAM-AMS Symposium in
Applied Mathematics Vol. 7
227:
223:
910:
377:
219:
305:
Examples of algorithms that require at least 2-EXPTIME include:
1017:
1012:
887:
870:
215:
1007:
1002:
823:
67:
297:. This can be generalized to higher and higher time bounds.
835:
693:
327:
Finding a complete set of associative-commutative unifiers
850:
782:
777:
698:
688:
436:"Super-Exponential Complexity of Presburger Arithmetic.
86:
255:
79:
623:"Complexity of Planning with Partial Observability"
313:provably requires at least doubly exponential time
289:
192:
1049:
620:
530:
487:
362:
654:
590:
661:
647:
130:
87:
591:Gruber, Hermann; Holzer, Markus (2008).
334:(which is, in fact, 2-EXPTIME-complete)
1050:
668:
418:. Section 20.1, corollary 3, page 495.
150:
147:
144:
141:
138:
110:
107:
104:
101:
98:
95:
92:
82:
642:
458:
410:, Computational Complexity (1994),
346:Cylindrical algebraic decomposition
344:takes doubly exponential time (see
13:
602:. Vol. 5126. pp. 39–50.
14:
1069:
1023:Probabilistically checkable proof
380:-complete to 2-EXPTIME-complete.
290:{\displaystyle 2^{2^{2^{n^{k}}}}}
18:computational complexity theory
614:
584:
524:
481:
452:
421:
401:
1:
395:
374:partially observable problems
309:Each decision procedure for
41:deterministic Turing machine
7:
608:10.1007/978-3-540-70583-3_4
390:Double exponential function
383:
363:2-EXPTIME-complete problems
300:
10:
1074:
1039:List of complexity classes
376:lifts the complexity from
244:alternating Turing machine
1036:
995:
959:
903:
796:
676:
462:SIAM Journal on Computing
1028:Interactive proof system
554:10.1007/3-540-45061-0_60
500:10.1109/LICS.1992.185515
621:Jussi Rintanen (2004).
982:Arithmetical hierarchy
632:. AAAI Press: 345–354.
408:Christos Papadimitriou
338:Quantifier elimination
291:
194:
977:Grzegorczyk hierarchy
972:Exponential hierarchy
904:Considered infeasible
537:Woeginger, Gerhard J.
322:worst-case complexity
311:Presburger arithmetic
292:
195:
967:Polynomial hierarchy
797:Suspected infeasible
253:
77:
996:Families of classes
677:Considered feasible
535:; Parrow, Joachim;
57:polynomial function
1058:Complexity classes
670:Complexity classes
533:Lenstra, Jan Karel
494:, pp. 11–21,
441:2006-09-15 at the
357:regular expression
342:real closed fields
287:
190:
135:
90:
27:(sometimes called
1045:
1044:
987:Boolean hierarchy
960:Class hierarchies
563:978-3-540-40493-4
416:978-0-201-53082-7
118:
89:
37:decision problems
1065:
663:
656:
649:
640:
639:
634:
633:
627:
618:
612:
611:
597:
588:
582:
580:
579:
578:
572:
566:, archived from
547:
528:
522:
520:
485:
479:
478:
456:
450:
432:Michael O. Rabin
425:
419:
405:
370:winning strategy
351:Calculating the
296:
294:
293:
288:
286:
285:
284:
283:
282:
281:
280:
279:
199:
197:
196:
191:
186:
182:
181:
180:
179:
178:
177:
154:
153:
134:
133:
114:
113:
91:
47:(2) time, where
22:complexity class
1073:
1072:
1068:
1067:
1066:
1064:
1063:
1062:
1048:
1047:
1046:
1041:
1032:
991:
955:
899:
893:PSPACE-complete
792:
672:
667:
637:
625:
619:
615:
595:
589:
585:
576:
574:
570:
564:
545:
529:
525:
510:
486:
482:
475:10.1137/0219053
457:
453:
443:Wayback Machine
426:
422:
406:
402:
398:
386:
365:
303:
275:
271:
270:
266:
265:
261:
260:
256:
254:
251:
250:
173:
169:
168:
164:
163:
159:
155:
137:
136:
129:
122:
85:
81:
80:
78:
75:
74:
12:
11:
5:
1071:
1061:
1060:
1043:
1042:
1037:
1034:
1033:
1031:
1030:
1025:
1020:
1015:
1010:
1005:
999:
997:
993:
992:
990:
989:
984:
979:
974:
969:
963:
961:
957:
956:
954:
953:
948:
943:
938:
933:
928:
923:
918:
913:
907:
905:
901:
900:
898:
897:
896:
895:
885:
880:
879:
878:
868:
863:
858:
853:
848:
843:
838:
833:
832:
831:
829:co-NP-complete
826:
821:
816:
806:
800:
798:
794:
793:
791:
790:
785:
780:
775:
770:
765:
760:
759:
758:
748:
743:
738:
733:
732:
731:
721:
716:
711:
706:
701:
696:
691:
686:
680:
678:
674:
673:
666:
665:
658:
651:
643:
636:
635:
613:
583:
562:
523:
508:
480:
469:(4): 750–773.
451:
428:Fischer, M. J.
420:
399:
397:
394:
393:
392:
385:
382:
364:
361:
360:
359:
349:
335:
328:
325:
314:
302:
299:
278:
274:
269:
264:
259:
240:
239:
201:
200:
189:
185:
176:
172:
167:
162:
158:
152:
149:
146:
143:
140:
132:
128:
125:
121:
117:
112:
109:
106:
103:
100:
97:
94:
84:
39:solvable by a
9:
6:
4:
3:
2:
1070:
1059:
1056:
1055:
1053:
1040:
1035:
1029:
1026:
1024:
1021:
1019:
1016:
1014:
1011:
1009:
1006:
1004:
1001:
1000:
998:
994:
988:
985:
983:
980:
978:
975:
973:
970:
968:
965:
964:
962:
958:
952:
949:
947:
944:
942:
939:
937:
934:
932:
929:
927:
924:
922:
919:
917:
914:
912:
909:
908:
906:
902:
894:
891:
890:
889:
886:
884:
881:
877:
874:
873:
872:
869:
867:
864:
862:
859:
857:
854:
852:
849:
847:
844:
842:
839:
837:
834:
830:
827:
825:
822:
820:
817:
815:
812:
811:
810:
807:
805:
802:
801:
799:
795:
789:
786:
784:
781:
779:
776:
774:
771:
769:
766:
764:
761:
757:
754:
753:
752:
749:
747:
744:
742:
739:
737:
734:
730:
727:
726:
725:
722:
720:
717:
715:
712:
710:
707:
705:
702:
700:
697:
695:
692:
690:
687:
685:
682:
681:
679:
675:
671:
664:
659:
657:
652:
650:
645:
644:
641:
631:
624:
617:
609:
605:
601:
594:
587:
573:on 2007-09-30
569:
565:
559:
555:
551:
544:
543:
538:
534:
527:
519:
515:
511:
509:0-8186-2735-2
505:
501:
497:
493:
492:
484:
476:
472:
468:
464:
463:
455:
448:
444:
440:
437:
433:
429:
424:
417:
413:
409:
404:
400:
391:
388:
387:
381:
379:
375:
371:
358:
354:
350:
347:
343:
339:
336:
333:
329:
326:
323:
319:
318:Gröbner basis
315:
312:
308:
307:
306:
298:
276:
272:
267:
262:
257:
247:
245:
237:
233:
229:
225:
221:
217:
213:
209:
206:
205:
204:
187:
183:
174:
170:
165:
160:
156:
126:
123:
119:
115:
73:
72:
71:
69:
64:
62:
58:
54:
50:
46:
42:
38:
34:
30:
26:
23:
19:
925:
629:
616:
599:
586:
575:, retrieved
568:the original
541:
526:
490:
483:
466:
460:
454:
446:
423:
403:
366:
316:Computing a
304:
248:
241:
231:
202:
66:In terms of
65:
60:
52:
48:
28:
24:
15:
876:#P-complete
814:NP-complete
729:NL-complete
330:Satisfying
931:ELEMENTARY
756:P-complete
577:2006-12-22
396:References
353:complement
236:ELEMENTARY
926:2-EXPTIME
518:206437926
434:, 1974, "
232:2-EXPTIME
127:∈
120:⋃
31:) is the
25:2-EXPTIME
1052:Category
921:EXPSPACE
916:NEXPTIME
684:DLOGTIME
539:(eds.),
439:Archived
384:See also
301:Examples
228:EXPSPACE
224:NEXPTIME
203:We know
911:EXPTIME
819:NP-hard
449:: 27–41
378:EXPTIME
220:EXPTIME
55:) is a
35:of all
1018:NSPACE
1013:DSPACE
888:PSPACE
560:
516:
506:
430:, and
414:
216:PSPACE
20:, the
1008:NTIME
1003:DTIME
824:co-NP
626:(PDF)
596:(PDF)
571:(PDF)
546:(PDF)
514:S2CID
355:of a
68:DTIME
29:2-EXP
836:TFNP
558:ISBN
504:ISBN
412:ISBN
951:ALL
851:QMA
841:FNP
783:APX
778:BQP
773:BPP
763:ZPP
694:ACC
604:doi
550:doi
496:doi
471:doi
340:on
332:CTL
59:of
43:in
33:set
16:In
1054::
946:RE
936:PR
883:IP
871:#P
866:PP
861:⊕P
856:PH
846:AM
809:NP
804:UP
788:FP
768:RP
746:CC
741:SC
736:NC
724:NL
719:FL
714:RL
709:SL
699:TC
689:AC
628:.
598:.
556:,
512:,
502:,
467:19
465:.
445:"
368:a
348:).
234:⊆
230:⊆
226:⊆
222:⊆
218:⊆
214:⊆
212:NP
210:⊆
70:,
63:.
941:R
751:P
704:L
662:e
655:t
648:v
610:.
606::
581:.
552::
521:.
498::
477:.
473::
277:k
273:n
268:2
263:2
258:2
238:.
208:P
188:.
184:)
175:k
171:n
166:2
161:2
157:(
151:E
148:M
145:I
142:T
139:D
131:N
124:k
116:=
111:E
108:M
105:I
102:T
99:P
96:X
93:E
88:-
83:2
61:n
53:n
51:(
49:p
45:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.