1352:
That is, the languages that can be recognized by deterministic polynomial-space Turing machines and nondeterministic polynomial-space Turing machines are the same. This follows directly from the fact that the square of a polynomial function is still a polynomial function. It is believed that a
205:
1331:. Thus by deciding connectivity in a graph representing nondeterministic Turing machine configurations, one can decide membership in the language recognized by that machine, in space proportional to the square of the space used by the Turing machine.
1470:
1240:
is set to a special vertex representing all accepting halting states. In this case, the algorithm returns true when the machine has a nondeterministic accepting path, and false otherwise. The number of configurations in this graph is
88:
1380:
1158:
317:
1102:
944:
1171:
This algorithm can be applied to an implicit graph whose vertices represent the configurations of a nondeterministic Turing machine and its tape, running within a given space bound
80:
1160:. The input graph is considered to be represented in a separate read-only memory and does not contribute to this auxiliary space bound. Alternatively, it may be represented as an
1329:
1284:
247:
can solve the same problem in the square of that space bound. Although it seems that nondeterminism may produce exponential gains in time (as formalized in the unproven
979:
1198:
241:
443:
is set large enough to impose no restriction on the paths (for instance, equal to the total number of vertices in the graph, or any larger value). To test for a
1238:
1218:
1063:
1043:
1023:
1003:
905:
601:
581:
561:
541:
521:
501:
481:
461:
441:
421:
401:
381:
361:
337:
1164:. Although described above in the form of a program in a high-level language, the same algorithm may be implemented with the same asymptotic space bound on a
1690:
1377:
That is, all languages that can be solved nondeterministically in logarithmic space can be solved deterministically in the complexity class
1685:
1546:
1656:
200:{\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right).}
1486:
264:
1638:
1575:
211:
20:
1111:
270:
1105:
1068:
910:
604:
244:
38:
248:
1538:
1465:{\displaystyle {\mathsf {\color {Blue}L}}^{2}={\mathsf {DSPACE}}\left(\left(\log n\right)^{2}\right).}
1289:
1244:
1563:
949:
1630:
1623:
711:"""Test whether a path of length at most k exists from s to t"""
1668:
251:), Savitch's theorem shows that it has a markedly more limited effect on space requirements.
1556:
1174:
217:
8:
642:"""Test whether a path of any length exists from s to t"""
1223:
1203:
1048:
1028:
1008:
988:
890:
586:
566:
546:
526:
506:
486:
466:
446:
426:
406:
386:
366:
346:
322:
1600:
1587:(1970). "Relationships between nondeterministic and deterministic tape complexities".
1286:, from which it follows that applying the algorithm to this implicit graph uses space
1663:
1634:
1571:
1542:
1353:
similar relationship does not exist between the polynomial time complexity classes,
1200:. The edges of this graph represent the nondeterministic transitions of the machine,
1604:
1596:
1552:
32:
1368:
1362:
1358:
260:
1618:
1584:
1372:
1354:
1165:
1161:
982:
343:
a somewhat more general problem, testing the existence of a path from a vertex
263:, the problem of determining whether there is a path between two vertices in a
28:
1609:
1679:
1530:
31:
in 1970, gives a relationship between deterministic and non-deterministic
1473:
340:
16:
Relation between deterministic and nondeterministic space complexity
1347:
1489: – Closure of nondeterministic space under complementation
1343:
423:
given as input. STCON is a special case of this problem where
1672:. Gives a historical account on how the proof was discovered.
503:, a deterministic algorithm can iterate through all vertices
523:, and recursively search for paths of half the length from
1220:
is set to the initial configuration of the machine, and
1657:
Foundations of
Complexity, Lesson 18: Savitch's Theorem
339:
vertices. The basic idea of the algorithm is to solve
1383:
1292:
1247:
1226:
1206:
1177:
1114:
1071:
1051:
1031:
1011:
991:
952:
913:
893:
589:
569:
549:
529:
509:
489:
469:
449:
429:
409:
389:
369:
349:
325:
273:
220:
91:
41:
603:. This algorithm can be expressed in pseudocode (in
1339:Some important corollaries of the theorem include:
1622:
1570:(1st ed.), Addison Wesley, pp. 149–150,
1464:
1323:
1278:
1232:
1212:
1192:
1152:
1096:
1057:
1037:
1017:
997:
973:
938:
899:
595:
575:
555:
535:
515:
495:
475:
455:
435:
415:
395:
375:
355:
331:
311:
235:
199:
74:
887:Because each recursive call halves the parameter
1677:
1566:(1993), "Section 7.3: The Reachability Method",
981:bits of storage for its function arguments and
1562:
1091:
1072:
933:
914:
1691:Theorems in computational complexity theory
1535:Computational complexity. A modern approach
1621:(1997), "Section 8.1: Savitch's Theorem",
1529:
1153:{\displaystyle O\left((\log n)^{2}\right)}
312:{\displaystyle O\left((\log n)^{2}\right)}
1625:Introduction to the Theory of Computation
1608:
1472:This follows from the fact that STCON is
1097:{\displaystyle \lceil \log _{2}n\rceil }
939:{\displaystyle \lceil \log _{2}n\rceil }
1589:Journal of Computer and System Sciences
1583:
907:, the number of levels of recursion is
1678:
1617:
1420:
1417:
1414:
1411:
1408:
1405:
1388:
158:
155:
152:
149:
146:
143:
109:
106:
103:
100:
97:
94:
1387:
259:The proof relies on an algorithm for
75:{\displaystyle f\in \Omega (\log(n))}
1508:
1499:
35:. It states that for any function
13:
48:
14:
1702:
1648:
212:nondeterministic Turing machine
21:computational complexity theory
1334:
1318:
1309:
1302:
1296:
1273:
1268:
1262:
1251:
1187:
1181:
1136:
1123:
968:
956:
295:
282:
230:
224:
69:
66:
60:
51:
1:
1601:10.1016/S0022-0000(70)80006-X
1514:Arora & Barak (2009) p.92
1505:Arora & Barak (2009) p.86
1493:
1487:Immerman–Szelepcsényi theorem
672:# n is the number of vertices
1686:Structural complexity theory
1361:, although this is still an
245:deterministic Turing machine
7:
1629:, PWS Publishing, pp.
1480:
1324:{\displaystyle O(f(n)^{2})}
1279:{\displaystyle O(2^{f(n)})}
249:exponential time hypothesis
10:
1707:
1539:Cambridge University Press
1106:auxiliary space complexity
214:can solve a problem using
974:{\displaystyle O(\log n)}
1568:Computational Complexity
609:
254:
1564:Papadimitriou, Christos
403:edges, for a parameter
1533:; Barak, Boaz (2009),
1466:
1325:
1280:
1234:
1214:
1194:
1154:
1098:
1059:
1039:
1019:
999:
975:
946:. Each level requires
940:
901:
597:
577:
557:
537:
517:
497:
477:
457:
437:
417:
397:
377:
357:
333:
313:
237:
201:
76:
1467:
1326:
1281:
1235:
1215:
1195:
1155:
1104:bits each. The total
1099:
1060:
1040:
1020:
1000:
976:
941:
902:
598:
578:
558:
538:
518:
498:
478:
458:
438:
418:
398:
378:
358:
334:
314:
238:
210:In other words, if a
202:
77:
1660:. Accessed 09/09/09.
1381:
1290:
1245:
1224:
1204:
1193:{\displaystyle f(n)}
1175:
1112:
1069:
1049:
1029:
1009:
989:
950:
911:
891:
607:syntax) as follows:
587:
567:
547:
527:
507:
487:
467:
447:
427:
407:
387:
367:
347:
323:
271:
236:{\displaystyle f(n)}
218:
89:
39:
1610:10338.dmlcz/120475
1585:Savitch, Walter J.
1462:
1391:
1321:
1276:
1230:
1210:
1190:
1150:
1094:
1055:
1035:
1015:
995:
971:
936:
897:
593:
573:
553:
533:
513:
493:
473:
453:
433:
413:
393:
383:that uses at most
373:
363:to another vertex
353:
329:
309:
233:
197:
72:
1669:Savitch’s Theorem
1664:Richard J. Lipton
1548:978-0-521-42426-4
1233:{\displaystyle t}
1213:{\displaystyle s}
1058:{\displaystyle u}
1038:{\displaystyle t}
1018:{\displaystyle s}
1005:and the vertices
998:{\displaystyle k}
900:{\displaystyle k}
596:{\displaystyle t}
576:{\displaystyle u}
556:{\displaystyle u}
536:{\displaystyle s}
516:{\displaystyle u}
496:{\displaystyle t}
476:{\displaystyle s}
456:{\displaystyle k}
436:{\displaystyle k}
416:{\displaystyle k}
396:{\displaystyle k}
376:{\displaystyle t}
356:{\displaystyle s}
332:{\displaystyle n}
25:Savitch's theorem
1698:
1643:
1628:
1614:
1612:
1580:
1559:
1515:
1512:
1506:
1503:
1471:
1469:
1468:
1463:
1458:
1454:
1453:
1448:
1444:
1424:
1423:
1399:
1398:
1393:
1392:
1330:
1328:
1327:
1322:
1317:
1316:
1285:
1283:
1282:
1277:
1272:
1271:
1239:
1237:
1236:
1231:
1219:
1217:
1216:
1211:
1199:
1197:
1196:
1191:
1159:
1157:
1156:
1151:
1149:
1145:
1144:
1143:
1103:
1101:
1100:
1095:
1084:
1083:
1064:
1062:
1061:
1056:
1044:
1042:
1041:
1036:
1024:
1022:
1021:
1016:
1004:
1002:
1001:
996:
980:
978:
977:
972:
945:
943:
942:
937:
926:
925:
906:
904:
903:
898:
883:
880:
877:
874:
871:
868:
865:
862:
859:
856:
853:
850:
847:
844:
841:
838:
835:
832:
829:
826:
823:
820:
817:
814:
811:
808:
805:
802:
799:
796:
793:
790:
787:
784:
781:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
718:
715:
712:
709:
706:
703:
700:
697:
694:
691:
688:
685:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
640:
637:
634:
631:
628:
625:
622:
619:
616:
613:
602:
600:
599:
594:
582:
580:
579:
574:
562:
560:
559:
554:
542:
540:
539:
534:
522:
520:
519:
514:
502:
500:
499:
494:
482:
480:
479:
474:
463:-edge path from
462:
460:
459:
454:
442:
440:
439:
434:
422:
420:
419:
414:
402:
400:
399:
394:
382:
380:
379:
374:
362:
360:
359:
354:
338:
336:
335:
330:
318:
316:
315:
310:
308:
304:
303:
302:
267:, which runs in
242:
240:
239:
234:
206:
204:
203:
198:
193:
189:
188:
187:
182:
162:
161:
137:
133:
132:
113:
112:
81:
79:
78:
73:
33:space complexity
1706:
1705:
1701:
1700:
1699:
1697:
1696:
1695:
1676:
1675:
1654:Lance Fortnow,
1651:
1646:
1641:
1619:Sipser, Michael
1578:
1549:
1518:
1513:
1509:
1504:
1500:
1496:
1483:
1449:
1434:
1430:
1429:
1425:
1404:
1403:
1394:
1386:
1385:
1384:
1382:
1379:
1378:
1337:
1312:
1308:
1291:
1288:
1287:
1258:
1254:
1246:
1243:
1242:
1225:
1222:
1221:
1205:
1202:
1201:
1176:
1173:
1172:
1139:
1135:
1122:
1118:
1113:
1110:
1109:
1079:
1075:
1070:
1067:
1066:
1050:
1047:
1046:
1030:
1027:
1026:
1010:
1007:
1006:
990:
987:
986:
983:local variables
951:
948:
947:
921:
917:
912:
909:
908:
892:
889:
888:
885:
884:
881:
878:
875:
872:
869:
866:
863:
860:
857:
854:
851:
848:
845:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
629:
626:
623:
620:
617:
614:
611:
588:
585:
584:
568:
565:
564:
548:
545:
544:
528:
525:
524:
508:
505:
504:
488:
485:
484:
468:
465:
464:
448:
445:
444:
428:
425:
424:
408:
405:
404:
388:
385:
384:
368:
365:
364:
348:
345:
344:
324:
321:
320:
298:
294:
281:
277:
272:
269:
268:
257:
219:
216:
215:
183:
172:
171:
167:
163:
142:
141:
122:
118:
114:
93:
92:
90:
87:
86:
40:
37:
36:
17:
12:
11:
5:
1704:
1694:
1693:
1688:
1674:
1673:
1661:
1650:
1649:External links
1647:
1645:
1644:
1639:
1615:
1595:(2): 177–192.
1581:
1576:
1560:
1547:
1531:Arora, Sanjeev
1526:
1525:
1524:
1522:
1517:
1516:
1507:
1497:
1495:
1492:
1491:
1490:
1482:
1479:
1478:
1477:
1461:
1457:
1452:
1447:
1443:
1440:
1437:
1433:
1428:
1422:
1419:
1416:
1413:
1410:
1407:
1402:
1397:
1390:
1375:
1366:
1350:
1336:
1333:
1320:
1315:
1311:
1307:
1304:
1301:
1298:
1295:
1275:
1270:
1267:
1264:
1261:
1257:
1253:
1250:
1229:
1209:
1189:
1186:
1183:
1180:
1166:Turing machine
1162:implicit graph
1148:
1142:
1138:
1134:
1131:
1128:
1125:
1121:
1117:
1093:
1090:
1087:
1082:
1078:
1074:
1054:
1034:
1014:
994:
970:
967:
964:
961:
958:
955:
935:
932:
929:
924:
920:
916:
896:
610:
592:
572:
552:
532:
512:
492:
472:
452:
432:
412:
392:
372:
352:
328:
307:
301:
297:
293:
290:
287:
284:
280:
276:
265:directed graph
256:
253:
232:
229:
226:
223:
208:
207:
196:
192:
186:
181:
178:
175:
170:
166:
160:
157:
154:
151:
148:
145:
140:
136:
131:
128:
125:
121:
117:
111:
108:
105:
102:
99:
96:
71:
68:
65:
62:
59:
56:
53:
50:
47:
44:
29:Walter Savitch
15:
9:
6:
4:
3:
2:
1703:
1692:
1689:
1687:
1684:
1683:
1681:
1671:
1670:
1665:
1662:
1659:
1658:
1653:
1652:
1642:
1640:0-534-94728-X
1636:
1632:
1627:
1626:
1620:
1616:
1611:
1606:
1602:
1598:
1594:
1590:
1586:
1582:
1579:
1577:0-201-53082-1
1573:
1569:
1565:
1561:
1558:
1554:
1550:
1544:
1540:
1536:
1532:
1528:
1527:
1523:
1520:
1519:
1511:
1502:
1498:
1488:
1485:
1484:
1475:
1459:
1455:
1450:
1445:
1441:
1438:
1435:
1431:
1426:
1400:
1395:
1376:
1374:
1370:
1367:
1364:
1363:open question
1360:
1356:
1351:
1349:
1345:
1342:
1341:
1340:
1332:
1313:
1305:
1299:
1293:
1265:
1259:
1255:
1248:
1227:
1207:
1184:
1178:
1169:
1167:
1163:
1146:
1140:
1132:
1129:
1126:
1119:
1115:
1107:
1088:
1085:
1080:
1076:
1052:
1032:
1012:
992:
984:
965:
962:
959:
953:
930:
927:
922:
918:
894:
608:
606:
590:
570:
550:
530:
510:
490:
470:
450:
430:
410:
390:
370:
350:
342:
326:
305:
299:
291:
288:
285:
278:
274:
266:
262:
252:
250:
246:
227:
221:
213:
194:
190:
184:
179:
176:
173:
168:
164:
138:
134:
129:
126:
123:
119:
115:
85:
84:
83:
63:
57:
54:
45:
42:
34:
30:
26:
22:
1667:
1655:
1624:
1592:
1588:
1567:
1534:
1510:
1501:
1338:
1170:
886:
258:
209:
27:, proved by
24:
18:
1474:NL-complete
1335:Corollaries
837:k_edge_path
798:k_edge_path
678:k_edge_path
648:k_edge_path
341:recursively
1680:Categories
1557:1193.68112
1494:References
319:space for
1439:
1130:
1092:⌉
1086:
1073:⌈
963:
934:⌉
928:
915:⌈
563:and from
289:
243:space, a
139:⊆
58:
49:Ω
46:∈
1481:See also
1108:is thus
1065:require
789:vertices
1631:279–281
1521:Sources
1348:NPSPACE
1637:
1574:
1555:
1545:
1344:PSPACE
1045:, and
879:return
873:return
756:return
729:return
645:return
605:Python
882:False
816:floor
777:edges
702:->
633:->
615:stcon
261:STCON
255:Proof
1635:ISBN
1572:ISBN
1543:ISBN
1357:and
876:True
855:ceil
705:bool
636:bool
1605:hdl
1597:doi
1553:Zbl
1436:log
1127:log
1077:log
960:log
919:log
870:)):
834:and
780:for
675:def
612:def
583:to
543:to
483:to
286:log
55:log
19:In
1682::
1666:,
1633:,
1603:.
1591:.
1551:,
1541:,
1537:,
1371:⊆
1369:NL
1359:NP
1346:=
1168:.
1025:,
985::
831:))
795:if
786:in
774:in
747:==
741:if
735:==
720:==
714:if
82:,
23:,
1613:.
1607::
1599::
1593:4
1476:.
1460:.
1456:)
1451:2
1446:)
1442:n
1432:(
1427:(
1421:E
1418:C
1415:A
1412:P
1409:S
1406:D
1401:=
1396:2
1389:L
1373:L
1365:.
1355:P
1319:)
1314:2
1310:)
1306:n
1303:(
1300:f
1297:(
1294:O
1274:)
1269:)
1266:n
1263:(
1260:f
1256:2
1252:(
1249:O
1228:t
1208:s
1188:)
1185:n
1182:(
1179:f
1147:)
1141:2
1137:)
1133:n
1124:(
1120:(
1116:O
1089:n
1081:2
1053:u
1033:t
1013:s
993:k
969:)
966:n
957:(
954:O
931:n
923:2
895:k
867:2
864:/
861:k
858:(
852:,
849:t
846:,
843:u
840:(
828:2
825:/
822:k
819:(
813:,
810:u
807:,
804:s
801:(
792::
783:u
771:)
768:t
765:,
762:s
759:(
753::
750:1
744:k
738:t
732:s
726::
723:0
717:k
708::
699:)
696:k
693:,
690:t
687:,
684:s
681:(
669:)
666:n
663:,
660:t
657:,
654:s
651:(
639::
630:)
627:t
624:,
621:s
618:(
591:t
571:u
551:u
531:s
511:u
491:t
471:s
451:k
431:k
411:k
391:k
371:t
351:s
327:n
306:)
300:2
296:)
292:n
283:(
279:(
275:O
231:)
228:n
225:(
222:f
195:.
191:)
185:2
180:)
177:n
174:(
169:f
165:(
159:E
156:C
153:A
150:P
147:S
144:D
135:)
130:)
127:n
124:(
120:f
116:(
110:E
107:C
104:A
101:P
98:S
95:N
70:)
67:)
64:n
61:(
52:(
43:f
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.