84:
consists of the languages that can be solved by a deterministic Turing machine with the same assumptions about tape length. Because there are only a polynomial number of distinct configurations of these machines, both
77:
that can be solved by a nondeterministic Turing machine with a read-only input tape and a separate read-write tape whose size is limited to be proportional to the logarithm of the input length. Similarly,
253:
and nondeterministically walk to every other reachable node. ST-connectivity can be seen to be NL-hard by considering the computation state graph of any other
257:
algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state.
118:
to it. Unless otherwise specified, the reductions in this definition are assumed to be many-one reductions by a deterministic logarithmic-space algorithm.
419:
206:
54:. If a deterministic algorithm exists for solving any one of the NL-complete problems in logarithmic memory space, then
781:
324:
412:
280:
43:
17:
225:(or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph
287:. Because of the Immerman–Szelepcsényi theorem, it follows that unique decipherability is also NL-complete.
182:
in language Y could be solved in logarithmic space by an algorithm that simulates the behavior of algorithm
283:
to show that the complementary problem, finding a string that has multiple ambiguous decodings, belongs to
816:
405:
797:
604:
369:; Lien, Y. Edmund; Laaser, William T (1976). "New problems complete for nondeterministic log space".
786:
265:
210:
740:
312:
291:
115:
735:
730:
29:
725:
358:
299:
272:
142:. For, suppose (by NL-completeness) that there existed a deterministic logspace reduction
8:
264:(Papadimitriou 1994 Thrm. 16.3), the problem of determining whether a boolean formula in
386:
745:
350:
320:
390:
709:
599:
531:
521:
428:
378:
346:
261:
194:), using the reduction algorithm to simulate each access to the read-only tape for
103:
74:
39:
25:
704:
694:
651:
641:
634:
624:
614:
572:
567:
562:
546:
526:
504:
499:
494:
482:
477:
472:
467:
354:
334:
295:
222:
50:. The NL-complete languages are the most "difficult" or "expressive" problems in
34:
699:
587:
509:
462:
95:
80:
47:
810:
366:
577:
689:
514:
382:
110:, and has the additional property that every other decision problem in
337:(1986), "The space complexity of the unique decipherability problem",
684:
397:
679:
674:
619:
442:
669:
776:
771:
646:
629:
213:
is NL-complete) then the language is also NL-complete itself.
766:
761:
582:
594:
452:
609:
541:
536:
457:
447:
209:
that, if a language is co-NL-complete (that is, if its
170:) that there exists a deterministic logspace algorithm
99:
of deterministic polynomial-time decision problems.
271:The problem of unique decipherability of a given
808:
365:
268:with two variables per clause is satisfiable.
413:
311:
420:
406:
319:. Reading, Massachusetts: Addison-Wesley.
260:Another important NL-complete problem is
245:. ST-connectivity can be seen to be in
809:
427:
333:
276:
401:
221:One important NL-complete problem is
134:, then so would every other language
237:on that graph, there is a path from
178:. With these assumptions, a problem
48:a logarithmic amount of memory space
290:Additional NL-complete problems on
162:, and also (by the assumption that
13:
275:was shown to be co-NL-complete by
106:is NL-complete when it belongs to
28:containing the languages that are
14:
828:
782:Probabilistically checkable proof
294:, Algebra, Linear System, Graph,
279:; Rytter used a variant of the
249:, because we start at the node
44:nondeterministic Turing machine
18:computational complexity theory
339:Information Processing Letters
65:
1:
305:
207:Immerman–Szelepcsényi theorem
121:
351:10.1016/0020-0190(86)90121-3
302:are listed in Jones (1976).
281:Sardinas–Patterson algorithm
7:
371:Mathematical Systems Theory
216:
126:If an NL-complete language
10:
833:
798:List of complexity classes
313:Papadimitriou, Christos H.
795:
754:
718:
662:
555:
435:
93:are subsets of the class
787:Interactive proof system
317:Computational Complexity
42:that can be solved by a
266:conjunctive normal form
741:Arithmetical hierarchy
146:that maps an instance
736:Grzegorczyk hierarchy
731:Exponential hierarchy
663:Considered infeasible
726:Polynomial hierarchy
556:Suspected infeasible
300:Context-free Grammar
273:variable-length code
205:It follows from the
174:for solving problem
755:Families of classes
436:Considered feasible
292:Propositional Logic
817:Complexity classes
429:Complexity classes
383:10.1007/BF01683259
804:
803:
746:Boolean hierarchy
719:Class hierarchies
75:decision problems
40:decision problems
824:
422:
415:
408:
399:
398:
394:
361:
335:Rytter, Wojciech
330:
262:2-satisfiability
130:could belong to
104:decision problem
73:consists of the
26:complexity class
832:
831:
827:
826:
825:
823:
822:
821:
807:
806:
805:
800:
791:
750:
714:
658:
652:PSPACE-complete
551:
431:
426:
327:
308:
296:Finite Automata
223:ST-connectivity
219:
154:to an instance
124:
68:
38:, the class of
12:
11:
5:
830:
820:
819:
802:
801:
796:
793:
792:
790:
789:
784:
779:
774:
769:
764:
758:
756:
752:
751:
749:
748:
743:
738:
733:
728:
722:
720:
716:
715:
713:
712:
707:
702:
697:
692:
687:
682:
677:
672:
666:
664:
660:
659:
657:
656:
655:
654:
644:
639:
638:
637:
627:
622:
617:
612:
607:
602:
597:
592:
591:
590:
588:co-NP-complete
585:
580:
575:
565:
559:
557:
553:
552:
550:
549:
544:
539:
534:
529:
524:
519:
518:
517:
507:
502:
497:
492:
491:
490:
480:
475:
470:
465:
460:
455:
450:
445:
439:
437:
433:
432:
425:
424:
417:
410:
402:
396:
395:
367:Jones, Neil D.
363:
331:
325:
307:
304:
229:and two nodes
218:
215:
123:
120:
67:
64:
9:
6:
4:
3:
2:
829:
818:
815:
814:
812:
799:
794:
788:
785:
783:
780:
778:
775:
773:
770:
768:
765:
763:
760:
759:
757:
753:
747:
744:
742:
739:
737:
734:
732:
729:
727:
724:
723:
721:
717:
711:
708:
706:
703:
701:
698:
696:
693:
691:
688:
686:
683:
681:
678:
676:
673:
671:
668:
667:
665:
661:
653:
650:
649:
648:
645:
643:
640:
636:
633:
632:
631:
628:
626:
623:
621:
618:
616:
613:
611:
608:
606:
603:
601:
598:
596:
593:
589:
586:
584:
581:
579:
576:
574:
571:
570:
569:
566:
564:
561:
560:
558:
554:
548:
545:
543:
540:
538:
535:
533:
530:
528:
525:
523:
520:
516:
513:
512:
511:
508:
506:
503:
501:
498:
496:
493:
489:
486:
485:
484:
481:
479:
476:
474:
471:
469:
466:
464:
461:
459:
456:
454:
451:
449:
446:
444:
441:
440:
438:
434:
430:
423:
418:
416:
411:
409:
404:
403:
400:
392:
388:
384:
380:
376:
372:
368:
364:
360:
356:
352:
348:
344:
340:
336:
332:
328:
326:0-201-53082-1
322:
318:
314:
310:
309:
303:
301:
297:
293:
288:
286:
282:
278:
277:Rytter (1986)
274:
269:
267:
263:
258:
256:
252:
248:
244:
240:
236:
232:
228:
224:
214:
212:
208:
203:
201:
197:
193:
189:
185:
181:
177:
173:
169:
165:
161:
157:
153:
149:
145:
141:
137:
133:
129:
119:
117:
113:
109:
105:
100:
98:
97:
92:
88:
83:
82:
76:
72:
63:
61:
58: =
57:
53:
49:
45:
41:
37:
36:
31:
27:
23:
19:
487:
374:
370:
342:
338:
316:
289:
284:
270:
259:
254:
250:
246:
242:
238:
234:
230:
226:
220:
204:
199:
195:
191:
187:
183:
179:
175:
171:
167:
163:
159:
155:
151:
147:
143:
139:
135:
131:
127:
125:
111:
107:
102:Formally, a
101:
94:
90:
86:
79:
70:
69:
59:
55:
51:
33:
21:
15:
635:#P-complete
573:NP-complete
488:NL-complete
377:(1): 1–17.
158:of problem
150:of problem
66:Definitions
22:NL-complete
690:ELEMENTARY
515:P-complete
345:(1): 1–3,
306:References
211:complement
122:Properties
685:2-EXPTIME
186:on input
811:Category
680:EXPSPACE
675:NEXPTIME
443:DLOGTIME
391:11530713
315:(1994).
217:Examples
30:complete
670:EXPTIME
578:NP-hard
359:0853618
116:reduced
114:can be
46:using
777:NSPACE
772:DSPACE
647:PSPACE
389:
357:
323:
166:is in
767:NTIME
762:DTIME
583:co-NP
387:S2CID
24:is a
595:TFNP
321:ISBN
233:and
202:).
89:and
32:for
710:ALL
610:QMA
600:FNP
542:APX
537:BQP
532:BPP
522:ZPP
453:ACC
379:doi
347:doi
241:to
138:in
16:In
813::
705:RE
695:PR
642:IP
630:#P
625:PP
620:⊕P
615:PH
605:AM
568:NP
563:UP
547:FP
527:RP
505:CC
500:SC
495:NC
483:NL
478:FL
473:RL
468:SL
458:TC
448:AC
385:.
375:10
373:.
355:MR
353:,
343:23
341:,
298:,
285:NL
255:NL
247:NL
140:NL
112:NL
108:NL
91:NL
71:NL
62:.
56:NL
52:NL
35:NL
20:,
700:R
510:P
463:L
421:e
414:t
407:v
393:.
381::
362:.
349::
329:.
251:s
243:t
239:s
235:t
231:s
227:G
200:y
198:(
196:r
192:y
190:(
188:r
184:A
180:y
176:X
172:A
168:L
164:X
160:X
156:x
152:Y
148:y
144:r
136:Y
132:L
128:X
96:P
87:L
81:L
60:L
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.