456:
280:
813:
Section 9.1.1: Exponential space completeness, pp. 313–317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete.
451:{\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}\left(2^{n^{k}}\right)=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}\left(2^{n^{k}}\right)}
91:
169:
120:
140:
682:
Wojciech Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip
Mazowiecki (2019). "The reachability problem for Petri nets is not elementary".
745:
838:
728:
209:
1200:
806:
831:
20:
681:
1235:
824:
1216:
1023:
1205:
51:
1159:
489:
with times (integer) and prove that the validity problem of their logic is EXPSPACE-complete.
1154:
1149:
648:
Charles
Rackoff (1978). "The covering and boundedness problems for vector addition systems".
512:
486:
1144:
504:
474:
represent different languages, where the expressions are limited to four operators: union,
190:
42:
145:
96:
8:
591:
The equivalence problem for regular expressions with squaring requires exponential space
706:
520:
471:
125:
664:
1164:
802:
795:
781:
764:
724:
630:
30:
482:(zero or more copies of an expression), and squaring (two copies of an expression).
1128:
1018:
950:
940:
847:
776:
716:
620:
586:
45:
34:
216:
that transforms instances of one to instances of the other with the same answer.
1123:
1113:
1070:
1060:
1053:
1043:
1033:
991:
986:
981:
965:
945:
923:
918:
913:
901:
896:
891:
886:
750:
720:
567:
542:
238:
172:
1118:
1006:
928:
881:
790:
698:
548:
244:
38:
1229:
634:
475:
590:
625:
608:
996:
906:
703:
2021 IEEE 62nd Annual
Symposium on Foundations of Computer Science (FOCS)
479:
1108:
933:
493:
1103:
816:
213:
699:"The Reachability Problem for Petri Nets is Not Primitive Recursive"
1093:
1038:
861:
711:
746:"An Easy-Sounding Problem Yields Numbers Too Big for Our Universe"
1088:
554:
250:
181:. If we use a nondeterministic machine instead, we get the class
1195:
1190:
1065:
1048:
536:
270:
264:
232:
177:
1185:
1180:
1001:
1013:
871:
1028:
960:
955:
876:
866:
220:
problems might be thought of as the hardest problems in
665:"The Reachability Problem Requires Exponential Space"
552:. It is further suspected to be a strict superset of
283:
148:
128:
99:
54:
595:
13th IEEE Symposium on
Switching and Automata Theory
175:, but most authors instead call the resulting class
212:to it. In other words, there is a polynomial-time
794:
470:problem is the problem of recognizing whether two
450:
163:
134:
114:
85:
607:Alur, Rajeev; Henzinger, Thomas A. (1994-01-01).
1227:
526:
647:
789:
832:
606:
248:and is believed to be a strict superset of
839:
825:
797:Introduction to the Theory of Computation
780:
710:
624:
395:
327:
743:
511:-hard for a long time, but shown to be
461:
1228:
846:
762:
696:
662:
418:
415:
412:
409:
406:
403:
350:
347:
344:
341:
338:
335:
307:
304:
301:
298:
295:
292:
289:
286:
820:
765:"The complexity of logical theories"
534:is known to be a strict superset of
257:
13:
210:polynomial-time many-one reduction
14:
1247:
1201:Probabilistically checkable proof
744:Brubaker, Ben (4 December 2023).
737:
690:
697:Leroux, Jerome (February 2022).
507:for Petri nets was known to be
21:computational complexity theory
763:Berman, Leonard (1 May 1980).
675:
656:
641:
600:
579:
158:
152:
109:
103:
80:
75:
69:
58:
1:
597:, Oct 1972, pp.125–129.
573:
558:, however this is not known.
527:Relationship to other classes
519:. In 2022 it was shown to be
492:The coverability problem for
782:10.1016/0304-3975(80)90037-7
769:Theoretical Computer Science
721:10.1109/FOCS52979.2021.00121
705:. IEEE. pp. 1241–1252.
650:Theoretical Computer Science
485:Alur and Henzinger extended
122:is a polynomial function of
37:solvable by a deterministic
7:
561:
86:{\displaystyle O(2^{p(n)})}
10:
1252:
1217:List of complexity classes
1214:
1173:
1137:
1081:
974:
854:
609:"A Really Temporal Logic"
1206:Interactive proof system
230:is a strict superset of
142:. Some authors restrict
16:Set of decision problems
204:, and every problem in
1160:Arithmetical hierarchy
452:
196:A decision problem is
165:
136:
116:
87:
1155:Grzegorczyk hierarchy
1150:Exponential hierarchy
1082:Considered infeasible
626:10.1145/174644.174651
515:, so probably not in
487:linear temporal logic
453:
166:
137:
117:
88:
1145:Polynomial hierarchy
975:Suspected infeasible
505:reachability problem
462:Examples of problems
281:
185:, which is equal to
164:{\displaystyle p(n)}
146:
126:
115:{\displaystyle p(n)}
97:
52:
1174:Families of classes
855:Considered feasible
669:Technical Report 62
663:Lipton, R. (1976).
472:regular expressions
1236:Complexity classes
848:Complexity classes
801:. PWS Publishing.
671:. Yale University.
448:
400:
332:
161:
132:
112:
83:
1223:
1222:
1165:Boolean hierarchy
1138:Class hierarchies
730:978-1-6654-2055-6
468:EXPSPACE-complete
466:An example of an
383:
315:
258:Formal definition
218:EXPSPACE-complete
198:EXPSPACE-complete
191:Savitch's theorem
135:{\displaystyle n}
35:decision problems
1243:
841:
834:
827:
818:
817:
812:
800:
786:
784:
756:
755:
741:
735:
734:
714:
694:
688:
687:
679:
673:
672:
660:
654:
653:
645:
639:
638:
628:
604:
598:
585:Meyer, A.R. and
583:
557:
551:
545:
539:
533:
518:
510:
499:
469:
457:
455:
454:
449:
447:
443:
442:
441:
440:
422:
421:
399:
398:
379:
375:
374:
373:
372:
354:
353:
331:
330:
311:
310:
273:
267:
253:
247:
241:
235:
229:
223:
219:
207:
203:
199:
188:
184:
180:
170:
168:
167:
162:
141:
139:
138:
133:
121:
119:
118:
113:
92:
90:
89:
84:
79:
78:
27:
1251:
1250:
1246:
1245:
1244:
1242:
1241:
1240:
1226:
1225:
1224:
1219:
1210:
1169:
1133:
1077:
1071:PSPACE-complete
970:
850:
845:
809:
759:
751:Quanta Magazine
742:
738:
731:
695:
691:
680:
676:
661:
657:
646:
642:
605:
601:
584:
580:
576:
568:Game complexity
564:
553:
547:
541:
535:
531:
529:
516:
508:
497:
467:
464:
436:
432:
431:
427:
423:
402:
401:
394:
387:
368:
364:
363:
359:
355:
334:
333:
326:
319:
285:
284:
282:
279:
278:
269:
263:
260:
249:
243:
237:
231:
227:
221:
217:
205:
201:
197:
186:
182:
176:
173:linear function
147:
144:
143:
127:
124:
123:
98:
95:
94:
65:
61:
53:
50:
49:
25:
17:
12:
11:
5:
1249:
1239:
1238:
1221:
1220:
1215:
1212:
1211:
1209:
1208:
1203:
1198:
1193:
1188:
1183:
1177:
1175:
1171:
1170:
1168:
1167:
1162:
1157:
1152:
1147:
1141:
1139:
1135:
1134:
1132:
1131:
1126:
1121:
1116:
1111:
1106:
1101:
1096:
1091:
1085:
1083:
1079:
1078:
1076:
1075:
1074:
1073:
1063:
1058:
1057:
1056:
1046:
1041:
1036:
1031:
1026:
1021:
1016:
1011:
1010:
1009:
1007:co-NP-complete
1004:
999:
994:
984:
978:
976:
972:
971:
969:
968:
963:
958:
953:
948:
943:
938:
937:
936:
926:
921:
916:
911:
910:
909:
899:
894:
889:
884:
879:
874:
869:
864:
858:
856:
852:
851:
844:
843:
836:
829:
821:
815:
814:
807:
791:Michael Sipser
787:
758:
757:
736:
729:
689:
674:
655:
640:
619:(1): 181–203.
599:
577:
575:
572:
571:
570:
563:
560:
528:
525:
463:
460:
459:
458:
446:
439:
435:
430:
426:
420:
417:
414:
411:
408:
405:
397:
393:
390:
386:
382:
378:
371:
367:
362:
358:
352:
349:
346:
343:
340:
337:
329:
325:
322:
318:
314:
309:
306:
303:
300:
297:
294:
291:
288:
259:
256:
160:
157:
154:
151:
131:
111:
108:
105:
102:
82:
77:
74:
71:
68:
64:
60:
57:
39:Turing machine
15:
9:
6:
4:
3:
2:
1248:
1237:
1234:
1233:
1231:
1218:
1213:
1207:
1204:
1202:
1199:
1197:
1194:
1192:
1189:
1187:
1184:
1182:
1179:
1178:
1176:
1172:
1166:
1163:
1161:
1158:
1156:
1153:
1151:
1148:
1146:
1143:
1142:
1140:
1136:
1130:
1127:
1125:
1122:
1120:
1117:
1115:
1112:
1110:
1107:
1105:
1102:
1100:
1097:
1095:
1092:
1090:
1087:
1086:
1084:
1080:
1072:
1069:
1068:
1067:
1064:
1062:
1059:
1055:
1052:
1051:
1050:
1047:
1045:
1042:
1040:
1037:
1035:
1032:
1030:
1027:
1025:
1022:
1020:
1017:
1015:
1012:
1008:
1005:
1003:
1000:
998:
995:
993:
990:
989:
988:
985:
983:
980:
979:
977:
973:
967:
964:
962:
959:
957:
954:
952:
949:
947:
944:
942:
939:
935:
932:
931:
930:
927:
925:
922:
920:
917:
915:
912:
908:
905:
904:
903:
900:
898:
895:
893:
890:
888:
885:
883:
880:
878:
875:
873:
870:
868:
865:
863:
860:
859:
857:
853:
849:
842:
837:
835:
830:
828:
823:
822:
819:
810:
808:0-534-94728-X
804:
799:
798:
792:
788:
783:
778:
774:
770:
766:
761:
760:
753:
752:
747:
740:
732:
726:
722:
718:
713:
708:
704:
700:
693:
685:
678:
670:
666:
659:
651:
644:
636:
632:
627:
622:
618:
614:
610:
603:
596:
592:
588:
587:L. Stockmeyer
582:
578:
569:
566:
565:
559:
556:
550:
544:
538:
524:
522:
514:
513:nonelementary
506:
501:
495:
490:
488:
483:
481:
477:
476:concatenation
473:
444:
437:
433:
428:
424:
391:
388:
384:
380:
376:
369:
365:
360:
356:
323:
320:
316:
312:
277:
276:
275:
272:
266:
255:
252:
246:
240:
234:
225:
215:
211:
194:
192:
179:
174:
155:
149:
129:
106:
100:
93:space, where
72:
66:
62:
55:
47:
44:
40:
36:
32:
28:
22:
1098:
796:
775:(1): 71–77.
772:
768:
749:
739:
702:
692:
683:
677:
668:
658:
649:
643:
616:
612:
602:
594:
581:
530:
502:
491:
484:
465:
262:In terms of
261:
226:
200:if it is in
195:
24:
18:
1054:#P-complete
992:NP-complete
907:NL-complete
523:-complete.
500:-complete.
480:Kleene star
48:, i.e., in
43:exponential
1109:ELEMENTARY
934:P-complete
712:2104.12695
652:: 223–231.
574:References
494:Petri Nets
1104:2-EXPTIME
635:0004-5411
521:Ackermann
392:∈
385:⋃
324:∈
317:⋃
214:algorithm
183:NEXPSPACE
1230:Category
1099:EXPSPACE
1094:NEXPTIME
862:DLOGTIME
793:(1997).
562:See also
532:EXPSPACE
517:EXPSPACE
509:EXPSPACE
498:EXPSPACE
228:EXPSPACE
222:EXPSPACE
206:EXPSPACE
202:EXPSPACE
187:EXPSPACE
171:to be a
26:EXPSPACE
1089:EXPTIME
997:NP-hard
684:STOC 19
555:EXPTIME
251:EXPTIME
33:of all
29:is the
1196:NSPACE
1191:DSPACE
1066:PSPACE
805:
727:
633:
613:J. ACM
546:, and
537:PSPACE
478:, the
271:NSPACE
265:DSPACE
242:, and
233:PSPACE
208:has a
178:ESPACE
1186:NTIME
1181:DTIME
1002:co-NP
707:arXiv
46:space
1014:TFNP
803:ISBN
725:ISBN
631:ISSN
503:The
268:and
1129:ALL
1029:QMA
1019:FNP
961:APX
956:BQP
951:BPP
941:ZPP
872:ACC
777:doi
717:doi
621:doi
496:is
189:by
41:in
31:set
19:In
1232::
1124:RE
1114:PR
1061:IP
1049:#P
1044:PP
1039:⊕P
1034:PH
1024:AM
987:NP
982:UP
966:FP
946:RP
924:CC
919:SC
914:NC
902:NL
897:FL
892:RL
887:SL
877:TC
867:AC
773:11
771:.
767:.
748:.
723:.
715:.
701:.
667:.
629:.
617:41
615:.
611:.
593:.
589:.
543:NP
540:,
274:,
254:.
239:NP
236:,
224:.
193:.
23:,
1119:R
929:P
882:L
840:e
833:t
826:v
811:.
785:.
779::
754:.
733:.
719::
709::
686:.
637:.
623::
549:P
445:)
438:k
434:n
429:2
425:(
419:E
416:C
413:A
410:P
407:S
404:N
396:N
389:k
381:=
377:)
370:k
366:n
361:2
357:(
351:E
348:C
345:A
342:P
339:S
336:D
328:N
321:k
313:=
308:E
305:C
302:A
299:P
296:S
293:P
290:X
287:E
245:P
159:)
156:n
153:(
150:p
130:n
110:)
107:n
104:(
101:p
81:)
76:)
73:n
70:(
67:p
63:2
59:(
56:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.