27:
327:
613:
699:. In this system, there is an all-powerful prover trying to convince a randomized polynomial-time verifier that a string is in the language. It should be able to convince the verifier with high probability if the string is in the language, but should not be able to convince it except with low probability if the string is not in the language.
831:. PSPACE-complete problems are of great importance to studying PSPACE problems because they represent the most difficult problems in PSPACE. Finding a simple solution to a PSPACE-complete problem would mean we have a simple solution to all other problems in PSPACE because all PSPACE problems could be reduced to a PSPACE-complete problem.
364:
608:{\displaystyle {\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subsetneq PSPACE\subsetneq EXPSPACE}}\\{\mathsf {P\subsetneq EXPTIME}}\end{array}}}
293:
618:
From the third line, it follows that both in the first and in the second line, at least one of the set containments must be strict, but it is not known which. It is widely suspected that all are strict.
119:
684:
operator. A full transitive closure is not needed; a commutative transitive closure and even weaker forms suffice. It is the addition of this operator that (possibly) distinguishes PSPACE from
817:
784:
125:
200:
1186:
1063:
835:
820:
1548:
1143:
1120:
1097:
904:
1179:
307:
132:
691:
A major result of complexity theory is that PSPACE can be characterized as all the languages recognizable by a particular
72:
1583:
1172:
1371:
622:
The containments in the third line are both known to be strict. The first follows from direct diagonalization (the
1564:
1055:
666:
299:
978:
Watrous, John; Aaronson, Scott (2009). "Closed timelike curves make quantum and classical computing equivalent".
1553:
692:
650:
623:
315:
1507:
1108:
673:
1502:
1497:
789:
756:
714:
1492:
997:
943:
627:
306:, NPSPACE is equivalent to PSPACE, essentially because a deterministic Turing machine can simulate a
303:
311:
1013:
987:
959:
933:
908:
681:
677:
646:
26:
1512:
1139:
1116:
1093:
1059:
1476:
1366:
1298:
1288:
1195:
1069:
1005:
951:
722:
703:
151:
140:
43:
1401:
326:
1471:
1461:
1418:
1408:
1391:
1381:
1339:
1334:
1329:
1313:
1293:
1271:
1266:
1261:
1249:
1244:
1239:
1234:
1073:
745:
734:
696:
685:
634:
347:
343:
335:
171:
51:
35:
20:
1001:
947:
288:{\displaystyle {\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {SPACE}}(n^{k}).}
1466:
1354:
1276:
1229:
1154:
1131:
1081:
339:
144:
31:
1577:
1086:
1047:
1159:
963:
980:
Proceedings of the Royal
Society A: Mathematical, Physical and Engineering Sciences
1017:
665:
An alternative characterization of PSPACE is the set of problems decidable by an
1344:
1254:
654:
318:
of all problems in PSPACE are also in PSPACE, meaning that co-PSPACE = PSPACE.
1456:
1281:
148:
1451:
955:
334:
The following relations are known between PSPACE and the complexity classes
60:
1009:
637:
for examples of problems that are suspected to be in PSPACE but not in NP.
1104:
Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
1446:
1441:
1386:
1209:
938:
369:
355:
1436:
928:
S. Aaronson (March 2005). "NP-complete problems and physical reality".
351:
1396:
633:
The hardest problems in PSPACE are the PSPACE-complete problems. See
358:(note that ⊊ denotes strict containment, not to be confused with ⊈):
19:"Polynomial space" redirects here. For for spaces of polynomials, see
1543:
1538:
1164:
47:
1533:
1528:
1349:
992:
913:
325:
39:
25:
1361:
1219:
1168:
630:. The second follows simply from the space hierarchy theorem.
1376:
1308:
1303:
1224:
1214:
749:
if it is in PSPACE and it is PSPACE-hard, which means for all
702:
PSPACE can be characterized as the quantum complexity class
330:
A representation of the relation among complexity classes
676:
theory is that it is the set of problems expressible in
669:
in polynomial time, sometimes called APTIME or just AP.
626:, NL ⊊ NPSPACE) and the fact that PSPACE = NPSPACE via
792:
759:
367:
203:
75:
298:
It turns out that allowing the Turing machine to be
114:{\displaystyle {\mathsf {P{\overset {?}{=}}PSPACE}}}
1521:
1485:
1429:
1322:
1202:
1085:
811:
778:
607:
287:
170:)), the set of all problems that can be solved by
113:
713:, problems solvable by classical computers using
1127:Chapter 19: Polynomial space, pp. 455–490.
834:An example of a PSPACE-complete problem is the
1180:
903:Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay;
310:without needing much more space (even though
8:
645:The class PSPACE is closed under operations
126:(more unsolved problems in computer science)
1138:(2nd ed.). Thomson Course Technology.
1052:Computational complexity. A modern approach
30:Inclusions of complexity classes including
1187:
1173:
1165:
672:A logical characterization of PSPACE from
302:does not add any extra power. Because of
1136:Introduction to the Theory of Computation
1088:Introduction to the Theory of Computation
991:
937:
912:
800:
791:
767:
758:
571:
570:
509:
508:
432:
431:
373:
372:
368:
366:
273:
248:
247:
241:
240:
233:
205:
204:
202:
81:
77:
76:
74:
194:, then we can define PSPACE formally as
859:
1029:
1027:
596:
593:
590:
587:
584:
581:
578:
572:
561:
558:
555:
552:
549:
546:
543:
540:
534:
531:
528:
525:
522:
519:
513:
510:
499:
496:
493:
490:
487:
484:
481:
478:
472:
469:
466:
463:
460:
457:
454:
448:
445:
442:
439:
436:
433:
422:
419:
416:
413:
410:
407:
401:
398:
392:
389:
383:
377:
374:
261:
258:
255:
252:
249:
221:
218:
215:
212:
209:
206:
106:
103:
100:
97:
94:
91:
86:
83:
78:
7:
63:Unsolved problem in computer science
836:quantified Boolean formula problem
821:polynomial-time many-one reduction
812:{\displaystyle A\leq _{\text{P}}B}
779:{\displaystyle A\leq _{\text{P}}B}
14:
1549:Probabilistically checkable proof
1115:(1st ed.). Addison Wesley.
308:nondeterministic Turing machine
133:computational complexity theory
893:Arora & Barak (2009) p.100
725:using closed timelike curves.
279:
266:
1:
1033:Arora & Barak (2009) p.83
907:(July 2009). "QIP = PSPACE".
884:Arora & Barak (2009) p.86
875:Arora & Barak (2009) p.85
866:Arora & Barak (2009) p.81
695:, the one defining the class
322:Relation among other classes
1150:Chapter 8: Space Complexity
186:)) space for some function
1600:
1565:List of complexity classes
1056:Cambridge University Press
732:
667:alternating Turing machine
18:
1562:
709:PSPACE is also equal to P
312:it may use much more time
1554:Interactive proof system
1113:Computational Complexity
838:(usually abbreviated to
693:interactive proof system
143:that can be solved by a
16:Set of decision problems
1109:Papadimitriou, Christos
956:10.1145/1052796.1052804
721:, problems solvable by
680:with the addition of a
661:Other characterizations
624:space hierarchy theorem
1508:Arithmetical hierarchy
1050:; Barak, Boaz (2009).
1010:10.1098/rspa.2008.0350
819:means that there is a
813:
780:
715:closed timelike curves
674:descriptive complexity
609:
331:
289:
162:If we denote by SPACE(
115:
58:
1503:Grzegorczyk hierarchy
1498:Exponential hierarchy
1430:Considered infeasible
814:
781:
610:
329:
290:
116:
29:
1493:Polynomial hierarchy
1323:Suspected infeasible
850:stands for "true").
790:
757:
365:
201:
73:
1522:Families of classes
1203:Considered feasible
1002:2009RSPSA.465..631A
948:2005quant.ph..2072A
729:PSPACE-completeness
717:, as well as to BQP
1584:Complexity classes
1196:Complexity classes
1092:. PWS Publishing.
809:
776:
682:transitive closure
678:second-order logic
641:Closure properties
605:
603:
332:
285:
246:
190:of the input size
139:is the set of all
111:
59:
1571:
1570:
1513:Boolean hierarchy
1486:Class hierarchies
1065:978-0-521-42426-4
803:
770:
723:quantum computers
628:Savitch's theorem
304:Savitch's theorem
229:
158:Formal definition
141:decision problems
89:
1591:
1189:
1182:
1175:
1166:
1149:
1126:
1103:
1091:
1077:
1034:
1031:
1022:
1021:
995:
975:
969:
967:
941:
939:quant-ph/0502072
925:
919:
918:
916:
900:
894:
891:
885:
882:
876:
873:
867:
864:
818:
816:
815:
810:
805:
804:
801:
785:
783:
782:
777:
772:
771:
768:
614:
612:
611:
606:
604:
600:
599:
565:
564:
503:
502:
426:
425:
300:nondeterministic
294:
292:
291:
286:
278:
277:
265:
264:
245:
244:
225:
224:
122:
120:
118:
117:
112:
110:
109:
90:
82:
64:
1599:
1598:
1594:
1593:
1592:
1590:
1589:
1588:
1574:
1573:
1572:
1567:
1558:
1517:
1481:
1425:
1419:PSPACE-complete
1318:
1198:
1193:
1146:
1132:Sipser, Michael
1130:
1123:
1107:
1100:
1082:Sipser, Michael
1080:
1066:
1046:
1043:
1038:
1037:
1032:
1025:
977:
976:
972:
927:
926:
922:
902:
901:
897:
892:
888:
883:
879:
874:
870:
865:
861:
856:
796:
788:
787:
763:
755:
754:
746:PSPACE-complete
737:
735:PSPACE-complete
731:
720:
712:
663:
651:complementation
643:
635:PSPACE-complete
602:
601:
567:
566:
505:
504:
428:
427:
363:
362:
324:
269:
199:
198:
172:Turing machines
160:
152:amount of space
129:
128:
123:
71:
70:
68:
66:
62:
24:
21:Polynomial ring
17:
12:
11:
5:
1597:
1595:
1587:
1586:
1576:
1575:
1569:
1568:
1563:
1560:
1559:
1557:
1556:
1551:
1546:
1541:
1536:
1531:
1525:
1523:
1519:
1518:
1516:
1515:
1510:
1505:
1500:
1495:
1489:
1487:
1483:
1482:
1480:
1479:
1474:
1469:
1464:
1459:
1454:
1449:
1444:
1439:
1433:
1431:
1427:
1426:
1424:
1423:
1422:
1421:
1411:
1406:
1405:
1404:
1394:
1389:
1384:
1379:
1374:
1369:
1364:
1359:
1358:
1357:
1355:co-NP-complete
1352:
1347:
1342:
1332:
1326:
1324:
1320:
1319:
1317:
1316:
1311:
1306:
1301:
1296:
1291:
1286:
1285:
1284:
1274:
1269:
1264:
1259:
1258:
1257:
1247:
1242:
1237:
1232:
1227:
1222:
1217:
1212:
1206:
1204:
1200:
1199:
1194:
1192:
1191:
1184:
1177:
1169:
1163:
1162:
1155:Complexity Zoo
1151:
1144:
1128:
1121:
1105:
1098:
1078:
1064:
1048:Arora, Sanjeev
1042:
1039:
1036:
1035:
1023:
970:
920:
895:
886:
877:
868:
858:
857:
855:
852:
808:
799:
795:
775:
766:
762:
733:Main article:
730:
727:
718:
710:
662:
659:
642:
639:
616:
615:
598:
595:
592:
589:
586:
583:
580:
577:
574:
569:
568:
563:
560:
557:
554:
551:
548:
545:
542:
539:
536:
533:
530:
527:
524:
521:
518:
515:
512:
507:
506:
501:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
453:
450:
447:
444:
441:
438:
435:
430:
429:
424:
421:
418:
415:
412:
409:
406:
403:
400:
397:
394:
391:
388:
385:
382:
379:
376:
371:
370:
323:
320:
314:). Also, the
296:
295:
284:
281:
276:
272:
268:
263:
260:
257:
254:
251:
243:
239:
236:
232:
228:
223:
220:
217:
214:
211:
208:
159:
156:
145:Turing machine
124:
108:
105:
102:
99:
96:
93:
88:
85:
80:
67:
61:
15:
13:
10:
9:
6:
4:
3:
2:
1596:
1585:
1582:
1581:
1579:
1566:
1561:
1555:
1552:
1550:
1547:
1545:
1542:
1540:
1537:
1535:
1532:
1530:
1527:
1526:
1524:
1520:
1514:
1511:
1509:
1506:
1504:
1501:
1499:
1496:
1494:
1491:
1490:
1488:
1484:
1478:
1475:
1473:
1470:
1468:
1465:
1463:
1460:
1458:
1455:
1453:
1450:
1448:
1445:
1443:
1440:
1438:
1435:
1434:
1432:
1428:
1420:
1417:
1416:
1415:
1412:
1410:
1407:
1403:
1400:
1399:
1398:
1395:
1393:
1390:
1388:
1385:
1383:
1380:
1378:
1375:
1373:
1370:
1368:
1365:
1363:
1360:
1356:
1353:
1351:
1348:
1346:
1343:
1341:
1338:
1337:
1336:
1333:
1331:
1328:
1327:
1325:
1321:
1315:
1312:
1310:
1307:
1305:
1302:
1300:
1297:
1295:
1292:
1290:
1287:
1283:
1280:
1279:
1278:
1275:
1273:
1270:
1268:
1265:
1263:
1260:
1256:
1253:
1252:
1251:
1248:
1246:
1243:
1241:
1238:
1236:
1233:
1231:
1228:
1226:
1223:
1221:
1218:
1216:
1213:
1211:
1208:
1207:
1205:
1201:
1197:
1190:
1185:
1183:
1178:
1176:
1171:
1170:
1167:
1161:
1157:
1156:
1152:
1147:
1145:0-534-95097-3
1141:
1137:
1133:
1129:
1124:
1122:0-201-53082-1
1118:
1114:
1110:
1106:
1101:
1099:0-534-94728-X
1095:
1090:
1089:
1083:
1079:
1075:
1071:
1067:
1061:
1057:
1053:
1049:
1045:
1044:
1040:
1030:
1028:
1024:
1019:
1015:
1011:
1007:
1003:
999:
994:
989:
986:(2102): 631.
985:
981:
974:
971:
965:
961:
957:
953:
949:
945:
940:
935:
931:
924:
921:
915:
910:
906:
899:
896:
890:
887:
881:
878:
872:
869:
863:
860:
853:
851:
849:
845:
841:
837:
832:
830:
826:
822:
806:
797:
793:
773:
764:
760:
752:
748:
747:
742:
736:
728:
726:
724:
716:
707:
705:
700:
698:
694:
689:
687:
683:
679:
675:
670:
668:
660:
658:
656:
652:
648:
640:
638:
636:
631:
629:
625:
620:
575:
537:
516:
475:
451:
404:
395:
386:
380:
361:
360:
359:
357:
353:
349:
345:
341:
337:
328:
321:
319:
317:
313:
309:
305:
301:
282:
274:
270:
237:
234:
230:
226:
197:
196:
195:
193:
189:
185:
181:
177:
173:
169:
165:
157:
155:
153:
150:
146:
142:
138:
134:
127:
57:
53:
49:
45:
41:
37:
33:
28:
22:
1413:
1153:
1135:
1112:
1087:
1051:
983:
979:
973:
929:
923:
905:John Watrous
898:
889:
880:
871:
862:
847:
843:
839:
833:
828:
824:
750:
744:
740:
738:
708:
701:
690:
671:
664:
644:
632:
621:
617:
333:
297:
191:
187:
183:
179:
175:
167:
163:
161:
136:
130:
55:
1402:#P-complete
1340:NP-complete
1255:NL-complete
930:SIGACT News
739:A language
655:Kleene star
316:complements
1457:ELEMENTARY
1282:P-complete
1074:1193.68112
1041:References
753:∈ PSPACE,
149:polynomial
1452:2-EXPTIME
993:0808.2669
914:0907.4737
798:≤
765:≤
576:⊊
538:⊊
517:⊊
476:⊆
452:⊆
405:⊆
396:⊆
387:⊆
381:⊆
238:∈
231:⋃
1578:Category
1447:EXPSPACE
1442:NEXPTIME
1210:DLOGTIME
1134:(2006).
1111:(1993).
1084:(1997).
964:18759797
786:, where
356:EXPSPACE
147:using a
1437:EXPTIME
1345:NP-hard
998:Bibcode
944:Bibcode
352:EXPTIME
121:
69:
1544:NSPACE
1539:DSPACE
1414:PSPACE
1160:PSPACE
1142:
1119:
1096:
1072:
1062:
1018:745646
1016:
962:
846:; the
653:, and
174:using
137:PSPACE
56:PSPACE
54:, and
48:P/poly
1534:NTIME
1529:DTIME
1350:co-NP
1014:S2CID
988:arXiv
960:S2CID
934:arXiv
909:arXiv
854:Notes
823:from
647:union
40:co-NP
1362:TFNP
1140:ISBN
1117:ISBN
1094:ISBN
1060:ISBN
844:TQBF
354:and
1477:ALL
1377:QMA
1367:FNP
1309:APX
1304:BQP
1299:BPP
1289:ZPP
1220:ACC
1070:Zbl
1006:doi
984:465
952:doi
842:or
840:QBF
827:to
743:is
719:CTC
711:CTC
704:QIP
131:In
44:BPP
1580::
1472:RE
1462:PR
1409:IP
1397:#P
1392:PP
1387:⊕P
1382:PH
1372:AM
1335:NP
1330:UP
1314:FP
1294:RP
1272:CC
1267:SC
1262:NC
1250:NL
1245:FL
1240:RL
1235:SL
1225:TC
1215:AC
1158::
1068:.
1058:.
1054:.
1026:^
1012:.
1004:.
996:.
982:.
958:.
950:.
942:.
932:.
706:.
697:IP
688:.
686:PH
657:.
649:,
350:,
348:PH
346:,
344:NP
342:,
338:,
336:NL
154:.
135:,
52:PH
50:,
46:,
42:,
38:,
36:NP
34:,
1467:R
1277:P
1230:L
1188:e
1181:t
1174:v
1148:.
1125:.
1102:.
1076:.
1020:.
1008::
1000::
990::
968:.
966:.
954::
946::
936::
917:.
911::
848:T
829:B
825:A
807:B
802:P
794:A
774:B
769:P
761:A
751:A
741:B
597:E
594:M
591:I
588:T
585:P
582:X
579:E
573:P
562:E
559:C
556:A
553:P
550:S
547:P
544:X
541:E
535:E
532:C
529:A
526:P
523:S
520:P
514:L
511:N
500:E
497:C
494:A
491:P
488:S
485:P
482:X
479:E
473:E
470:M
467:I
464:T
461:P
458:X
455:E
449:E
446:C
443:A
440:P
437:S
434:P
423:E
420:C
417:A
414:P
411:S
408:P
402:H
399:P
393:P
390:N
384:P
378:L
375:N
340:P
283:.
280:)
275:k
271:n
267:(
262:E
259:C
256:A
253:P
250:S
242:N
235:k
227:=
222:E
219:C
216:A
213:P
210:S
207:P
192:n
188:f
184:n
182:(
180:f
178:(
176:O
168:n
166:(
164:f
107:E
104:C
101:A
98:P
95:S
92:P
87:?
84:=
79:P
65::
32:P
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
