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