84:
74:
53:
256:
179:
158:
22:
506:
I just added a section to explain why logspace theory can be usefull outside of the computational world, but I have no practical example, if someone has got any link it could be usefull. (The problem beeing mostly that since examples would be of impossibility, it wouldn't have "real life" use, the
499:
I appear to be too stupid to figure out how to use the citation system, but the citation is in the references, namely
Reingold's paper. If the flag is asking for the fact that the result appeared in October 2004 (which apparently was significant since someone else proved a worse bound a few weeks
277:
552:
Planar graph isomorphism -- Samir Datta, Nutan Limaye, Prajakta
Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar Graph Isomorphism is in Log-Space. In Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity (CCC '09).
301:
140:
441:
539:
This page really should have a section on L-complete problems. I will try and add some later when I have more time. However, if anybody wants to beat me to it, here are some:
549:
SAT(2) (CNF-SAT where each variable occurs at most twice) -- Jan
Johannsen. Satisfiability Problems Complete for Deterministic Logarithmic Space. In Proceedings of STACS'2004.
358:
296:
580:
I think the page should also contain opinions on that, and what the equality or inequality would entail. We have that kind of info in the article for the much better known
622:
229:
219:
627:
617:
195:
612:
403:
130:
607:
377:
242:
186:
163:
106:
523:
466:
560:
349:
330:
97:
58:
422:
501:
387:
268:
33:
397:
311:
432:
194:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
519:
459:
21:
507:
logspace algorithm one can see in complexity are of no real world use because of their uge time complexity)
564:
368:
39:
83:
556:
515:
511:
581:
105:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
589:
89:
73:
52:
287:
339:
191:
502:
http://blog.computationalcomplexity.org/2004/11/undirected-connectivity-in-log-space.html
413:
255:
278:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
601:
585:
102:
79:
320:
178:
157:
546:
Undirected reachability follows from L=SL (and is already in the article).
593:
568:
527:
576:
Opinions about the likelihood and consequences of L = P and/or L≠P
396:
Find pictures for the biographies of computer scientists (see
15:
543:
Deterministic reachability is perhaps the canonical one.
190:, a collaborative effort to improve the coverage of
101:, a collaborative effort to improve the coverage of
302:Computer science articles needing expert attention
442:WikiProject Computer science/Unreferenced BLPs
8:
359:Computer science articles without infoboxes
297:Computer science articles needing attention
19:
263:Here are some tasks awaiting attention:
237:
152:
47:
623:Mid-importance Computer science articles
154:
49:
204:Knowledge:WikiProject Computer science
628:WikiProject Computer science articles
618:Start-Class Computer science articles
207:Template:WikiProject Computer science
7:
184:This article is within the scope of
95:This article is within the scope of
38:It is of interest to the following
378:Timeline of computing 2020–present
14:
613:Mid-priority mathematics articles
404:Computing articles needing images
115:Knowledge:WikiProject Mathematics
608:Start-Class mathematics articles
254:
177:
156:
118:Template:WikiProject Mathematics
82:
72:
51:
20:
224:This article has been rated as
135:This article has been rated as
1:
458:Tag all relevant articles in
198:and see a list of open tasks.
109:and see a list of open tasks.
594:23:12, 9 November 2012 (UTC)
467:WikiProject Computer science
243:WikiProject Computer science
187:WikiProject Computer science
398:List of computer scientists
644:
230:project's importance scale
460:Category:Computer science
236:
223:
210:Computer science articles
172:
134:
67:
46:
569:14:18, 9 June 2011 (UTC)
528:23:35, 17 May 2010 (UTC)
462:and sub-categories with
141:project's priority scale
98:WikiProject Mathematics
500:after Reingold), see
423:Computer science stubs
28:This article is rated
241:Things you can help
121:mathematics articles
582:P versus NP problem
535:L-complete problems
90:Mathematics portal
34:content assessment
559:comment added by
531:
514:comment added by
497:
496:
493:
492:
489:
488:
485:
484:
481:
480:
151:
150:
147:
146:
635:
571:
530:
508:
471:
465:
340:Computer science
269:Article requests
258:
251:
250:
238:
212:
211:
208:
205:
202:
201:Computer science
192:Computer science
181:
174:
173:
168:
164:Computer science
160:
153:
123:
122:
119:
116:
113:
92:
87:
86:
76:
69:
68:
63:
55:
48:
31:
25:
24:
16:
643:
642:
638:
637:
636:
634:
633:
632:
598:
597:
578:
554:
537:
516:Arthur MILCHIOR
509:
477:
474:
469:
463:
451:Project-related
446:
427:
408:
382:
363:
344:
325:
306:
282:
209:
206:
203:
200:
199:
166:
120:
117:
114:
111:
110:
88:
81:
61:
32:on Knowledge's
29:
12:
11:
5:
641:
639:
631:
630:
625:
620:
615:
610:
600:
599:
577:
574:
573:
572:
550:
547:
544:
536:
533:
495:
494:
491:
490:
487:
486:
483:
482:
479:
478:
476:
475:
473:
472:
455:
447:
445:
444:
438:
428:
426:
425:
419:
409:
407:
406:
401:
393:
383:
381:
380:
374:
364:
362:
361:
355:
345:
343:
342:
336:
326:
324:
323:
317:
307:
305:
304:
299:
293:
283:
281:
280:
274:
262:
260:
259:
247:
246:
234:
233:
226:Mid-importance
222:
216:
215:
213:
196:the discussion
182:
170:
169:
167:Mid‑importance
161:
149:
148:
145:
144:
133:
127:
126:
124:
107:the discussion
94:
93:
77:
65:
64:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
640:
629:
626:
624:
621:
619:
616:
614:
611:
609:
606:
605:
603:
596:
595:
591:
587:
583:
575:
570:
566:
562:
561:71.192.228.96
558:
551:
548:
545:
542:
541:
540:
534:
532:
529:
525:
521:
517:
513:
504:
503:
468:
461:
457:
456:
454:
452:
448:
443:
440:
439:
437:
435:
434:
429:
424:
421:
420:
418:
416:
415:
410:
405:
402:
399:
395:
394:
392:
390:
389:
384:
379:
376:
375:
373:
371:
370:
365:
360:
357:
356:
354:
352:
351:
346:
341:
338:
337:
335:
333:
332:
327:
322:
319:
318:
316:
314:
313:
308:
303:
300:
298:
295:
294:
292:
290:
289:
284:
279:
276:
275:
273:
271:
270:
265:
264:
261:
257:
253:
252:
249:
248:
244:
240:
239:
235:
231:
227:
221:
218:
217:
214:
197:
193:
189:
188:
183:
180:
176:
175:
171:
165:
162:
159:
155:
142:
138:
132:
129:
128:
125:
108:
104:
100:
99:
91:
85:
80:
78:
75:
71:
70:
66:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
579:
555:— Preceding
538:
505:
498:
450:
449:
433:Unreferenced
431:
430:
412:
411:
386:
385:
367:
366:
348:
347:
329:
328:
310:
309:
286:
285:
267:
266:
225:
185:
137:Mid-priority
136:
96:
62:Mid‑priority
40:WikiProjects
510:—Preceding
112:Mathematics
103:mathematics
59:Mathematics
30:Start-class
602:Categories
321:Computing
586:Tijfo098
557:unsigned
524:contribs
512:unsigned
369:Maintain
312:Copyedit
350:Infobox
288:Cleanup
228:on the
139:on the
331:Expand
36:scale.
414:Stubs
388:Photo
245:with:
590:talk
565:talk
520:talk
220:Mid
131:Mid
604::
592:)
584:.
567:)
526:)
522:•
470:}}
464:{{
588:(
563:(
518:(
453::
436::
417::
400:)
391::
372::
353::
334::
315::
291::
272::
232:.
143:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
