910:, according to which NL is closed under complements, the one-sided error in these probabilistic computations can be replaced by zero-sided error. That is, these problems can be solved by probabilistic Turing machines that use logarithmic space and never make errors. The corresponding complexity class that also requires the machine to use only polynomial time is called
747:
This was the strongest deterministic-space inclusion known in 1994 (Papadimitriou 1994 Problem 16.4.10, "Symmetric space"). Since larger space classes are not affected by quadratic increases, the nondeterministic and deterministic classes are known to be equal, so that for example we have
742:
949:
and Abuzer Yakaryılmaz have proven that the deterministic logarithmic-space Turing machine in the statement above can be replaced by a bounded-error probabilistic constant-space Turing machine that is allowed to use only a constant number of random bits.
415:
566:
942:
if and only if such a Turing machine accepts any word in the language for an appropriate choice of certificate in its additional input tape, and rejects any word not in the language regardless of the certificate.
820:, is not limited to polynomial time, because although it has a polynomial number of configurations it can use randomness to escape an infinite loop. If we do limit it to polynomial time, we get the class
62:
637:
163:
Important results in complexity theory allow us to relate this complexity class with other classes, telling us about the relative power of the resources involved. Results in the field of
631:, which tells us that any nondeterministic algorithm can be simulated by a deterministic machine in at most quadratically more space. From Savitch's theorem, we have directly that:
298:
592:, the class of problems solvable by randomized algorithms in logarithmic space and unbounded time, with no error. It is not, however, known or believed to be equal to
286:
903:
to take 2 steps on average before stopping. It only needs to keep a running total of the number of heads in a row it sees, which it can count in log space.
911:
600:
506:
167:, on the other hand, tell us which problems can be solved with this resource. Like much of complexity theory, many important questions about
68:
938:. Consider a deterministic logarithmic-space bounded Turing machine that has an additional read-only read-once input tape. A language is in
1145:
891:
The only problem is that we don't have room in log space for a binary counter that goes up to 2. To get around this we replace it with a
888:, and because there are 2 computation paths in all, we have a good chance of hitting the accepting one (bounded below by a constant).
1113:
1021:
176:
107:
907:
468:
737:{\displaystyle {\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{equivalently, }}{\mathsf {NL\subseteq L}}^{2}.}
27:
1507:
1104:
1074:
1138:
127:
99:
75:
979:
787:
that never accept incorrectly but are allowed to reject incorrectly less than 1/3 of the time; this is called
784:
268:
of two literals, if there is a variable assignment that makes the formula true. An example instance, where
123:
1542:
1131:
1523:
1330:
917:
Thus, when we only look at space, it seems that randomization and nondeterminism are equally powerful.
436:
410:{\displaystyle (x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})}
1512:
929:
476:
1087:(27 June 1997). "Sections 8.4–8.6: The Classes L and NL, NL-completeness, NL equals coNL".
460:
978:
The class NL is closed under the operations complementation, union, and therefore intersection,
1466:
145:
1096:
1089:
899:
coins and stops and rejects if they all land on heads. Since this event has probability 2, we
1461:
1456:
1451:
628:
271:
8:
261:
217:
967:
487:
1036:
A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness,"
1471:
1100:
1070:
1017:
963:
780:
1435:
1325:
1257:
1247:
1154:
776:
594:
588:
440:
257:
225:
95:
91:
1430:
1420:
1377:
1367:
1360:
1350:
1340:
1298:
1293:
1288:
1272:
1252:
1230:
1225:
1220:
1203:
1198:
1193:
1011:
934:
822:
578:
496:
229:
221:
195:
1059:
1425:
1313:
1235:
1188:
1084:
1054:
900:
816:
431:
241:
118:
853:
If the string is not in the language, both reject along all computation paths.
480:
1536:
1003:
472:
15:
249:
172:
1303:
1213:
983:
561:{\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}
265:
212:
1415:
1240:
1007:
884:, and execute this 2 times. Because no computation path exceeds length
1410:
1123:
864:
algorithm accepts along at least two-thirds of its computation paths.
164:
103:
1405:
1400:
1345:
1168:
1395:
946:
754:
1502:
1497:
1372:
1355:
750:
144:
can be formally defined in terms of the computational resource
194:
below; however, this name is more frequently used to refer to
1492:
1487:
1308:
860:
algorithm accepts along at least one computation path and a
1320:
1178:
1065:
Papadimitriou, C. (1994). "Chapter 16: Logarithmic Space".
826:, which is contained in but not known or believed to equal
500:
1335:
1267:
1262:
1183:
1173:
880:
algorithm and choose a random computation path of length
962:: it contains precisely those languages expressible in
640:
509:
301:
274:
30:
126:. Since any deterministic Turing machine is also a
17:
1088:
833:There is a simple algorithm that establishes that
736:
560:
409:
280:
56:
1534:
57:{\displaystyle {\mathsf {L{\overset {?}{=}}NL}}}
1083:
958:There is a simple logical characterization of
1139:
1064:
191:
1114:Introduction to Complexity Theory: Lecture 7
69:(more unsolved problems in computer science)
766:
1146:
1132:
1002:
761:
1120:is what Goldreich calls badRSPACE(log n).
1091:Introduction to the Theory of Computation
953:
920:
1116:. Oded Goldreich. Proposition 6.1. Our
814:, unlike its deterministic counterpart
205:
122:, the class for logspace problems on a
1535:
1153:
783:solvable in logarithmithic space with
720:
714:
711:
664:
661:
658:
655:
652:
646:
643:
604:, the polynomial-time restrictions of
551:
547:
543:
537:
534:
528:
520:
516:
512:
49:
46:
41:
38:
33:
1127:
973:
928:can equivalently be characterised by
856:If the string is in the language, an
791:. The constant 1/3 is arbitrary; any
177:Unsolved problems in computer science
1013:Complexity Theory: A Modern Approach
264:formula of which each clause is the
18:Unsolved problem in computer science
1038:Logical Methods in Computer Science
471:) was independently discovered by
13:
391:
375:
340:
318:
275:
14:
1554:
1508:Probabilistically checkable proof
612:, which some authors refer to as
210:Several problems are known to be
479:in 1987; they received the 1995
459:is the class of languages whose
932:, analogous to classes such as
420:
128:nondeterministic Turing machine
100:nondeterministic Turing machine
76:computational complexity theory
1030:
1016:. Cambridge University Press.
996:
688:
669:
443:, but it is not known whether
404:
372:
366:
337:
331:
302:
198:, which is not known to equal
1:
1047:
1040:, Vol. 10(3:6)2014, pp. 1-17.
908:Immerman–Szelepcsényi theorem
785:probabilistic Turing machines
627:to deterministic space using
469:Immerman–Szelepcsényi theorem
895:counter, which simply flips
196:randomized logarithmic space
124:deterministic Turing machine
7:
1095:. PWS Publishing. pp.
1010:(2009). "Definition 4.19".
10:
1559:
1524:List of complexity classes
1521:
1480:
1444:
1388:
1281:
1161:
494:can be placed within the
437:polynomial-time algorithm
90:ogarithmic-space) is the
1513:Interactive proof system
1067:Computational Complexity
989:
799:< 1/2 would suffice.
767:Probabilistic definition
192:probabilistic definition
98:that can be solved by a
762:Alternative definitions
116:is a generalization of
1467:Arithmetical hierarchy
954:Descriptive complexity
921:Certificate definition
738:
562:
411:
282:
146:nondeterministic space
58:
1462:Grzegorczyk hierarchy
1457:Exponential hierarchy
1389:Considered infeasible
739:
563:
412:
283:
281:{\displaystyle \neg }
59:
1452:Polynomial hierarchy
1282:Suspected infeasible
876:, we simply take an
638:
507:
299:
272:
218:log-space reductions
206:NL-complete problems
28:
1481:Families of classes
1162:Considered feasible
705:equivalently,
582:. It is known that
477:Róbert Szelepcsényi
467:. This result (the
451:. It is known that
435:, since there is a
1543:Complexity classes
1155:Complexity classes
1069:. Addison-Wesley.
974:Closure properties
968:transitive closure
802:It turns out that
734:
558:
488:circuit complexity
407:
278:
186:is referred to as
54:
1530:
1529:
1472:Boolean hierarchy
1445:Class hierarchies
1023:978-0-521-42426-4
964:first-order logic
781:decision problems
706:
702:
699:
696:
693:
629:Savitch's theorem
425:It is known that
96:decision problems
44:
1550:
1148:
1141:
1134:
1125:
1124:
1110:
1094:
1080:
1041:
1034:
1028:
1027:
1000:
872:is contained in
845:is contained in
777:complexity class
757:
743:
741:
740:
735:
730:
729:
724:
723:
707:
704:
700:
697:
694:
691:
681:
680:
668:
667:
626:
619:
615:
611:
607:
603:
597:
591:
585:
581:
576:is contained in
575:
572:More precisely,
567:
565:
564:
559:
557:
556:
555:
554:
524:
523:
499:
493:
466:
458:
454:
450:
446:
441:2-satisfiability
434:
429:is contained in
428:
416:
414:
413:
408:
403:
402:
387:
386:
365:
364:
352:
351:
330:
329:
314:
313:
287:
285:
284:
279:
258:2-satisfiability
232:asks, for nodes
226:2-satisfiability
134:is contained in
92:complexity class
86:ondeterministic
65:
63:
61:
60:
55:
53:
52:
45:
37:
19:
1558:
1557:
1553:
1552:
1551:
1549:
1548:
1547:
1533:
1532:
1531:
1526:
1517:
1476:
1440:
1384:
1378:PSPACE-complete
1277:
1157:
1152:
1107:
1077:
1050:
1045:
1044:
1035:
1031:
1024:
1001:
997:
992:
976:
956:
923:
906:Because of the
789:one-sided error
769:
764:
749:
725:
710:
709:
708:
703:
676:
672:
642:
641:
639:
636:
635:
624:
617:
613:
609:
605:
599:
593:
587:
583:
577:
573:
550:
546:
519:
515:
511:
510:
508:
505:
504:
495:
491:
483:for this work.
464:
456:
452:
448:
444:
430:
426:
423:
398:
394:
382:
378:
360:
356:
347:
343:
325:
321:
309:
305:
300:
297:
296:
273:
270:
269:
230:ST-connectivity
222:ST-connectivity
208:
148:(or NSPACE) as
130:, we have that
72:
71:
66:
36:
32:
31:
29:
26:
25:
23:
21:
12:
11:
5:
1556:
1546:
1545:
1528:
1527:
1522:
1519:
1518:
1516:
1515:
1510:
1505:
1500:
1495:
1490:
1484:
1482:
1478:
1477:
1475:
1474:
1469:
1464:
1459:
1454:
1448:
1446:
1442:
1441:
1439:
1438:
1433:
1428:
1423:
1418:
1413:
1408:
1403:
1398:
1392:
1390:
1386:
1385:
1383:
1382:
1381:
1380:
1370:
1365:
1364:
1363:
1353:
1348:
1343:
1338:
1333:
1328:
1323:
1318:
1317:
1316:
1314:co-NP-complete
1311:
1306:
1301:
1291:
1285:
1283:
1279:
1278:
1276:
1275:
1270:
1265:
1260:
1255:
1250:
1245:
1244:
1243:
1233:
1228:
1223:
1218:
1217:
1216:
1206:
1201:
1196:
1191:
1186:
1181:
1176:
1171:
1165:
1163:
1159:
1158:
1151:
1150:
1143:
1136:
1128:
1122:
1121:
1111:
1105:
1085:Michael Sipser
1081:
1075:
1062:
1055:Complexity Zoo
1049:
1046:
1043:
1042:
1029:
1022:
1004:Arora, Sanjeev
994:
993:
991:
988:
975:
972:
966:with an added
955:
952:
922:
919:
866:
865:
854:
810:. Notice that
768:
765:
763:
760:
745:
744:
733:
728:
722:
719:
716:
713:
690:
687:
684:
679:
675:
671:
666:
663:
660:
657:
654:
651:
648:
645:
623:We can relate
570:
569:
553:
549:
545:
542:
539:
536:
533:
530:
527:
522:
518:
514:
422:
419:
418:
417:
406:
401:
397:
393:
390:
385:
381:
377:
374:
371:
368:
363:
359:
355:
350:
346:
342:
339:
336:
333:
328:
324:
320:
317:
312:
308:
304:
277:
260:asks, given a
242:directed graph
207:
204:
67:
51:
48:
43:
40:
35:
22:
16:
9:
6:
4:
3:
2:
1555:
1544:
1541:
1540:
1538:
1525:
1520:
1514:
1511:
1509:
1506:
1504:
1501:
1499:
1496:
1494:
1491:
1489:
1486:
1485:
1483:
1479:
1473:
1470:
1468:
1465:
1463:
1460:
1458:
1455:
1453:
1450:
1449:
1447:
1443:
1437:
1434:
1432:
1429:
1427:
1424:
1422:
1419:
1417:
1414:
1412:
1409:
1407:
1404:
1402:
1399:
1397:
1394:
1393:
1391:
1387:
1379:
1376:
1375:
1374:
1371:
1369:
1366:
1362:
1359:
1358:
1357:
1354:
1352:
1349:
1347:
1344:
1342:
1339:
1337:
1334:
1332:
1329:
1327:
1324:
1322:
1319:
1315:
1312:
1310:
1307:
1305:
1302:
1300:
1297:
1296:
1295:
1292:
1290:
1287:
1286:
1284:
1280:
1274:
1271:
1269:
1266:
1264:
1261:
1259:
1256:
1254:
1251:
1249:
1246:
1242:
1239:
1238:
1237:
1234:
1232:
1229:
1227:
1224:
1222:
1219:
1215:
1212:
1211:
1210:
1207:
1205:
1202:
1200:
1197:
1195:
1192:
1190:
1187:
1185:
1182:
1180:
1177:
1175:
1172:
1170:
1167:
1166:
1164:
1160:
1156:
1149:
1144:
1142:
1137:
1135:
1130:
1129:
1126:
1119:
1115:
1112:
1108:
1106:0-534-94728-X
1102:
1098:
1093:
1092:
1086:
1082:
1078:
1076:0-201-53082-1
1072:
1068:
1063:
1061:
1057:
1056:
1052:
1051:
1039:
1033:
1025:
1019:
1015:
1014:
1009:
1005:
999:
995:
987:
985:
981:
980:concatenation
971:
969:
965:
961:
951:
948:
944:
941:
937:
936:
931:
927:
918:
915:
913:
909:
904:
902:
898:
894:
889:
887:
883:
879:
875:
871:
868:To show that
863:
859:
855:
852:
851:
850:
848:
844:
840:
836:
831:
829:
825:
824:
819:
818:
813:
809:
805:
800:
798:
794:
790:
786:
782:
778:
774:
759:
756:
752:
731:
726:
717:
685:
682:
677:
673:
649:
634:
633:
632:
630:
621:
602:
596:
590:
580:
540:
531:
525:
503:
502:
501:
498:
489:
484:
482:
478:
474:
473:Neil Immerman
470:
462:
442:
438:
433:
399:
395:
388:
383:
379:
369:
361:
357:
353:
348:
344:
334:
326:
322:
315:
310:
306:
295:
294:
293:
291:
267:
263:
262:propositional
259:
255:
251:
247:
243:
239:
235:
231:
227:
223:
219:
215:
214:
203:
201:
197:
193:
189:
185:
182:Occasionally
180:
178:
174:
170:
166:
161:
159:
155:
151:
147:
143:
139:
137:
133:
129:
125:
121:
120:
115:
111:
109:
105:
101:
97:
93:
89:
85:
81:
77:
70:
1208:
1117:
1090:
1066:
1053:
1037:
1032:
1012:
998:
977:
959:
957:
945:
939:
933:
930:certificates
925:
924:
916:
905:
896:
892:
890:
885:
881:
877:
873:
869:
867:
861:
857:
846:
842:
838:
834:
832:
827:
821:
815:
811:
807:
803:
801:
796:
792:
788:
772:
770:
746:
622:
586:is equal to
571:
485:
424:
421:Containments
292:, might be:
289:
253:
245:
237:
233:
220:, including
211:
209:
199:
187:
183:
181:
168:
162:
157:
153:
149:
141:
140:
135:
131:
117:
113:
112:
108:memory space
87:
83:
79:
73:
1361:#P-complete
1299:NP-complete
1214:NL-complete
1008:Barak, Boaz
984:Kleene star
481:Gödel Prize
461:complements
447:or whether
266:disjunction
213:NL-complete
190:due to its
104:logarithmic
94:containing
1416:ELEMENTARY
1241:P-complete
1048:References
970:operator.
893:randomized
841:. Clearly
453:NL = co-NL
288:indicates
244:, whether
171:are still
165:algorithms
106:amount of
1411:2-EXPTIME
849:, since:
795:with 0 ≤
718:⊆
683:
650:⊆
541:⊆
532:⊆
526:⊆
392:¬
389:∨
376:¬
370:∧
354:∨
341:¬
335:∧
319:¬
316:∨
276:¬
250:reachable
1537:Category
1406:EXPSPACE
1401:NEXPTIME
1169:DLOGTIME
771:Suppose
455:, where
102:using a
1396:EXPTIME
1304:NP-hard
1097:294–302
947:Cem Say
775:is the
755:NPSPACE
463:are in
64:
24:
1503:NSPACE
1498:DSPACE
1373:PSPACE
1103:
1073:
1020:
982:, and
901:expect
751:PSPACE
701:
698:
695:
692:
449:L = NL
445:NL = P
216:under
154:NSPACE
1493:NTIME
1488:DTIME
1309:co-NP
990:Notes
457:co-NL
252:from
240:in a
175:(see
156:(log
1321:TFNP
1101:ISBN
1071:ISBN
1018:ISBN
912:ZPLP
616:and
608:and
601:ZPLP
475:and
439:for
236:and
224:and
173:open
1436:ALL
1336:QMA
1326:FNP
1268:APX
1263:BQP
1258:BPP
1248:ZPP
1179:ACC
779:of
674:log
618:ZPL
610:ZPL
598:or
595:RLP
589:ZPL
486:In
290:not
248:is
228:.
179:).
160:).
74:In
1539::
1431:RE
1421:PR
1368:IP
1356:#P
1351:PP
1346:⊕P
1341:PH
1331:AM
1294:NP
1289:UP
1273:FP
1253:RP
1231:CC
1226:SC
1221:NC
1209:NL
1204:FL
1199:RL
1194:SL
1184:TC
1174:AC
1099:.
1060:NL
1058::
1006:;
986:.
960:NL
940:NL
935:NP
926:NL
914:.
878:NL
870:NL
858:NL
847:NL
839:NL
837:=
830:.
828:NL
823:RL
808:NL
806:=
758:.
753:=
625:NL
620:.
614:RL
606:RL
584:NL
579:AC
574:NL
497:NC
492:NL
490:,
465:NL
427:NL
256:.
202:.
200:NL
188:RL
184:NL
169:NL
152:=
150:NL
142:NL
138:.
136:NL
114:NL
110:.
80:NL
78:,
1426:R
1236:P
1189:L
1147:e
1140:t
1133:v
1118:C
1109:.
1079:.
1026:.
897:n
886:n
882:n
874:C
862:C
843:C
835:C
817:L
812:C
804:C
797:x
793:x
773:C
732:.
727:2
721:L
715:L
712:N
689:)
686:n
678:2
670:(
665:E
662:C
659:A
656:P
653:S
647:L
644:N
568:.
552:2
548:C
544:N
538:L
535:N
529:L
521:1
517:C
513:N
432:P
405:)
400:2
396:x
384:1
380:x
373:(
367:)
362:3
358:x
349:2
345:x
338:(
332:)
327:3
323:x
311:1
307:x
303:(
254:S
246:T
238:T
234:S
158:n
132:L
119:L
88:L
84:N
82:(
50:L
47:N
42:?
39:=
34:L
20::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.