87:, since for the former, it is required that a single algorithm runs in both polynomial time and polylogarithmic space; while for the latter, two separate algorithms will suffice: one that runs in polynomial time, and another that runs in polylogarithmic space. (It is unknown whether
349:
289:
380:
777:
235:
S. A. Cook. Deterministic CFL's are accepted simultaneously in polynomial time and log squared space. Proceedings of ACM STOC'79, pp. 338–345. 1979.
103:
342:
742:
373:
112:
20:
335:
179:
315:
36:
782:
366:
565:
758:
747:
701:
696:
691:
108:
686:
151:
272:
706:
283:
670:
560:
492:
482:
389:
264:
174:
32:
595:
665:
655:
612:
602:
585:
575:
533:
528:
523:
507:
487:
465:
455:
443:
438:
433:
428:
187:
168:
156:
135:
119:, as shown by Cook in 1979. It is open if all context-free languages can be recognized in
660:
548:
470:
423:
319:
219:
52:
41:
771:
244:
276:
28:
538:
448:
224:
650:
475:
256:
183:
645:
268:
640:
635:
580:
403:
630:
261:
Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92)
590:
737:
732:
607:
358:
727:
722:
543:
47:
555:
413:
362:
570:
502:
497:
418:
408:
263:, Victoria, British Columbia, Canada, pp. 619–623,
323:
715:
679:
623:
516:
396:
245:TCS Stack Exchange: CFG parsing using o(n^2) space
374:
343:
8:
198:space, a deterministic machine can simulate
381:
367:
359:
350:
336:
288:: CS1 maint: location missing publisher (
182:in logarithmic space and polynomial time.
211:
281:
178:are classes of problems acceptable by
7:
303:
301:
45:) and polylogarithmic space (class
778:Theoretical computer science stubs
190:result that both are contained in
154:). This question is equivalent to
14:
743:Probabilistically checkable proof
202:space probabilistic algorithms.
150:(because of a DFS algorithm and
142:, although it is known to be in
123:, although they are known be in
113:deterministic pushdown automata
21:computational complexity theory
75:. Note that the definition of
1:
180:probabilistic Turing machines
322:. You can help Knowledge by
316:theoretical computer science
73:deterministic time and space
37:deterministic Turing machine
27:(Steve's Class, named after
59:)) space for some constant
799:
759:List of complexity classes
300:
39:in polynomial time (class
35:of problems solvable by a
756:
63:). It may also be called
748:Interactive proof system
194:. In other words, given
186:showed in 1992 the weak
134:It is open if directed
107:, the strict subset of
702:Arithmetical hierarchy
318:–related article is a
109:context-free languages
697:Grzegorczyk hierarchy
692:Exponential hierarchy
624:Considered infeasible
269:10.1145/129712.129772
687:Polynomial hierarchy
517:Suspected infeasible
65:DTISP(poly, polylog)
716:Families of classes
397:Considered feasible
259:(1992), "RL ⊆ SC",
783:Complexity classes
390:Complexity classes
115:, is contained in
765:
764:
707:Boolean hierarchy
680:Class hierarchies
331:
330:
152:Savitch's theorem
99:are equivalent).
790:
383:
376:
369:
360:
352:
345:
338:
307:P ≟ NP
302:
295:
293:
287:
279:
253:
247:
242:
236:
233:
227:
216:
33:complexity class
16:Complexity class
798:
797:
793:
792:
791:
789:
788:
787:
768:
767:
766:
761:
752:
711:
675:
619:
613:PSPACE-complete
512:
392:
387:
357:
356:
309:
299:
298:
280:
255:
254:
250:
243:
239:
234:
230:
217:
213:
208:
196:polylogarithmic
188:derandomization
136:st-connectivity
17:
12:
11:
5:
796:
794:
786:
785:
780:
770:
769:
763:
762:
757:
754:
753:
751:
750:
745:
740:
735:
730:
725:
719:
717:
713:
712:
710:
709:
704:
699:
694:
689:
683:
681:
677:
676:
674:
673:
668:
663:
658:
653:
648:
643:
638:
633:
627:
625:
621:
620:
618:
617:
616:
615:
605:
600:
599:
598:
588:
583:
578:
573:
568:
563:
558:
553:
552:
551:
549:co-NP-complete
546:
541:
536:
526:
520:
518:
514:
513:
511:
510:
505:
500:
495:
490:
485:
480:
479:
478:
468:
463:
458:
453:
452:
451:
441:
436:
431:
426:
421:
416:
411:
406:
400:
398:
394:
393:
388:
386:
385:
378:
371:
363:
355:
354:
347:
340:
332:
329:
328:
311:
305:
297:
296:
248:
237:
228:
220:Complexity Zoo
210:
209:
207:
204:
111:recognized by
15:
13:
10:
9:
6:
4:
3:
2:
795:
784:
781:
779:
776:
775:
773:
760:
755:
749:
746:
744:
741:
739:
736:
734:
731:
729:
726:
724:
721:
720:
718:
714:
708:
705:
703:
700:
698:
695:
693:
690:
688:
685:
684:
682:
678:
672:
669:
667:
664:
662:
659:
657:
654:
652:
649:
647:
644:
642:
639:
637:
634:
632:
629:
628:
626:
622:
614:
611:
610:
609:
606:
604:
601:
597:
594:
593:
592:
589:
587:
584:
582:
579:
577:
574:
572:
569:
567:
564:
562:
559:
557:
554:
550:
547:
545:
542:
540:
537:
535:
532:
531:
530:
527:
525:
522:
521:
519:
515:
509:
506:
504:
501:
499:
496:
494:
491:
489:
486:
484:
481:
477:
474:
473:
472:
469:
467:
464:
462:
459:
457:
454:
450:
447:
446:
445:
442:
440:
437:
435:
432:
430:
427:
425:
422:
420:
417:
415:
412:
410:
407:
405:
402:
401:
399:
395:
391:
384:
379:
377:
372:
370:
365:
364:
361:
353:
348:
346:
341:
339:
334:
333:
327:
325:
321:
317:
312:
308:
304:
291:
285:
278:
274:
270:
266:
262:
258:
252:
249:
246:
241:
238:
232:
229:
226:
222:
221:
215:
212:
205:
203:
201:
197:
193:
189:
185:
181:
177:
176:
171:
170:
165:
163:
159:
158:
153:
149:
145:
141:
137:
132:
130:
126:
122:
118:
114:
110:
106:
105:
100:
98:
94:
90:
86:
82:
79:differs from
78:
74:
70:
66:
62:
58:
54:
50:
49:
44:
43:
38:
34:
30:
26:
22:
460:
324:expanding it
313:
306:
260:
251:
240:
231:
218:
214:
199:
195:
191:
173:
167:
166:
161:
155:
147:
143:
139:
133:
128:
124:
120:
116:
102:
101:
96:
92:
88:
84:
80:
76:
72:
68:
64:
60:
56:
51:) (that is,
46:
40:
29:Stephen Cook
24:
18:
596:#P-complete
534:NP-complete
449:NL-complete
257:Nisan, Noam
200:logarithmic
71:stands for
772:Categories
651:ELEMENTARY
476:P-complete
206:References
184:Noam Nisan
646:2-EXPTIME
31:) is the
641:EXPSPACE
636:NEXPTIME
404:DLOGTIME
284:citation
277:11651375
146:∩
127:∩
95:∩
83:∩
67:, where
631:EXPTIME
539:NP-hard
738:NSPACE
733:DSPACE
608:PSPACE
310:
275:
138:is in
55:((log
728:NTIME
723:DTIME
544:co-NP
314:This
273:S2CID
148:PolyL
129:PolyL
97:PolyL
85:PolyL
69:DTISP
48:PolyL
556:TFNP
320:stub
290:link
172:and
104:DCFL
91:and
671:ALL
571:QMA
561:FNP
503:APX
498:BQP
493:BPP
483:ZPP
414:ACC
265:doi
175:BPL
19:In
774::
666:RE
656:PR
603:IP
591:#P
586:PP
581:⊕P
576:PH
566:AM
529:NP
524:UP
508:FP
488:RP
466:CC
461:SC
456:NC
444:NL
439:FL
434:RL
429:SL
419:TC
409:AC
286:}}
282:{{
271:,
225:SC
223::
192:SC
169:RL
164:.
162:SC
160:⊆
157:NL
140:SC
131:.
121:SC
117:SC
89:SC
77:SC
25:SC
23:,
661:R
471:P
424:L
382:e
375:t
368:v
351:e
344:t
337:v
326:.
294:.
292:)
267::
144:P
125:P
93:P
81:P
61:k
57:n
53:O
42:P
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.