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