95:
85:
64:
267:
190:
169:
33:
595:
555:
515:
805:
You might consider emailing
Immerman directly -- I emailed him a couple years ago about FO(REGULAR) and he was kind enough to explain the definition directly to me :) By the way, good work on the article so far, it's looking much improved. Lead probably needs a rewrite to be more accessible, I will
789:
Indeed, SO(LFP) is depicted as EXPTIME on the illustration on the cover of
Immerman (1999). However, I couldn't find any discussion of it inside the book, and Ebbinghaus and Flum (Finite model theory, 2nd Ed. 1999, Theorem 8.5.1) say that SO(PFP), which should certainly be at least as expressive as
288:
723:
In my opinion, a much better organisation would be to order the characterisations by the complexity classes they are representing, and by the classes of structures on which they are representing them. The first step would be to merge the existing articles into
820:
Thank you very much for your suggestion, and your kind words! Any improvements to the lead (or elsewhere) would be highly appreciated – I just tried to rearrange, smooth out and verify what was there already, and I am sure one can do better at several
720:(ESO = NP) holds on all classes of finite structures, while the Immermann-Vardi Theorem (FO(LFP) = P) holds only for ordered structures, and Grädel's theorem (Second-order Horn logic = P) only holds in the presence of a successor relation.
639:
can be used to describe complexity classes? Traversal of Kripke structures etc. I know the complexities of showing satisfiability in different modal logics; how does that relate to classes of languages expressible in those logics?
715:
make little sense without that context. Most problematically, however, none of the descriptions adequately distinguish between the classes of structures on which a given characterisation holds. For instance,
312:
774:
Analogously to first-order least-fixed point logic, second-order logic can be augmented by a least-fixed point operator that takes second-order variables as arguments. SO(LFP) is to SO what
151:
452:
369:
307:
865:
240:
230:
691:, but which really is a stubby list of characterisations of complexity classes. Then we have three pages giving more detailed description of these characterisations,
824:
In fact, I will hopefully be attending an algorithmic and finite model theory workshop in March, so I could also use this puzzle for some breaktime discussion :).
870:
206:
860:
855:
414:
141:
388:
253:
197:
174:
117:
850:
477:
360:
341:
108:
69:
433:
762:
Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.
725:
688:
611:
571:
531:
398:
279:
44:
408:
322:
687:
The current coverage of descriptive complexity is quite unsatisfactory. We have what should be the parent article,
443:
205:
related articles on
Knowledge. If you would like to participate, please visit the project page, where you can join
470:
790:
SO(LFP), reduces to FO(PFP) (which equals PSPACE) on ordered structures. Any insight would be much appreciated!
811:
748:
379:
50:
94:
621:
581:
541:
32:
807:
744:
614:
on
February 2022. For the contribution history and old versions of the redirected page, please see
574:
on
February 2022. For the contribution history and old versions of the redirected page, please see
534:
on
February 2022. For the contribution history and old versions of the redirected page, please see
116:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
829:
795:
733:
100:
84:
63:
607:
567:
527:
298:
782:. The LFP operator can now also take second-order variable as argument. SO(LFP) is equal to
717:
350:
202:
833:
815:
799:
752:
737:
649:
779:
775:
712:
708:
704:
700:
696:
692:
645:
424:
266:
289:
Requested articles/Applied arts and sciences/Computer science, computing, and
Internet
844:
825:
791:
729:
17:
636:
113:
90:
641:
331:
189:
168:
783:
589:
549:
509:
407:
Find pictures for the biographies of computer scientists (see
26:
771:
The page on SO (complexity) contained the following section:
806:
try to take a pass sometime if I get some free time for it.
679:
since there was nothing but support for more than a week.
616:
602:
576:
562:
536:
522:
669:
Subsequent comments should be made in a new section.
201:, a collaborative effort to improve the coverage of
112:, a collaborative effort to improve the coverage of
313:Computer science articles needing expert attention
453:WikiProject Computer science/Unreferenced BLPs
672:A summary of the conclusions reached follows.
8:
620:; for the discussion at that location, see
580:; for the discussion at that location, see
540:; for the discussion at that location, see
370:Computer science articles without infoboxes
308:Computer science articles needing attention
274:Here are some tasks awaiting attention:
248:
163:
58:
866:Low-importance Computer science articles
728:, and then we could take it from there.
165:
60:
30:
215:Knowledge:WikiProject Computer science
871:WikiProject Computer science articles
218:Template:WikiProject Computer science
7:
663:The following discussion is closed.
195:This article is within the scope of
106:This article is within the scope of
49:It is of interest to the following
703:. The main context is provided at
389:Timeline of computing 2020–present
25:
861:C-Class Computer science articles
856:Mid-priority mathematics articles
415:Computing articles needing images
126:Knowledge:WikiProject Mathematics
758:The discussion above is closed.
593:
553:
513:
265:
188:
167:
129:Template:WikiProject Mathematics
93:
83:
62:
31:
635:Does anyone know how different
235:This article has been rated as
146:This article has been rated as
1:
834:22:53, 15 February 2022 (UTC)
816:22:19, 15 February 2022 (UTC)
800:21:40, 15 February 2022 (UTC)
726:Descriptive complexity theory
689:Descriptive complexity theory
612:Descriptive complexity theory
572:Descriptive complexity theory
532:Descriptive complexity theory
469:Tag all relevant articles in
209:and see a list of open tasks.
120:and see a list of open tasks.
851:C-Class mathematics articles
753:01:53, 7 February 2022 (UTC)
738:19:01, 6 February 2022 (UTC)
478:WikiProject Computer science
254:WikiProject Computer science
198:WikiProject Computer science
409:List of computer scientists
887:
241:project's importance scale
650:14:05, 8 March 2010 (UTC)
471:Category:Computer science
247:
234:
221:Computer science articles
183:
145:
78:
57:
760:Please do not modify it.
743:Agreed on all accounts.
666:Please do not modify it.
473:and sub-categories with
152:project's priority scale
109:WikiProject Mathematics
707:rather than here, and
434:Computer science stubs
39:This article is rated
600:The contents of the
560:The contents of the
520:The contents of the
252:Things you can help
132:mathematics articles
18:Talk:HO (complexity)
101:Mathematics portal
45:content assessment
628:
627:
588:
587:
548:
547:
508:
507:
504:
503:
500:
499:
496:
495:
492:
491:
162:
161:
158:
157:
16:(Redirected from
878:
668:
619:
597:
596:
590:
579:
557:
556:
550:
539:
517:
516:
510:
482:
476:
351:Computer science
280:Article requests
269:
262:
261:
249:
223:
222:
219:
216:
213:
212:Computer science
203:Computer science
192:
185:
184:
179:
175:Computer science
171:
164:
134:
133:
130:
127:
124:
103:
98:
97:
87:
80:
79:
74:
66:
59:
42:
36:
35:
27:
21:
886:
885:
881:
880:
879:
877:
876:
875:
841:
840:
769:
764:
763:
718:Fagin's theorem
713:HO (complexity)
709:SO (complexity)
705:FO (complexity)
701:HO (complexity)
697:SO (complexity)
693:FO (complexity)
685:
664:
657:
633:
615:
603:HO (complexity)
594:
575:
563:SO (complexity)
554:
535:
523:FO (complexity)
514:
488:
485:
480:
474:
462:Project-related
457:
438:
419:
393:
374:
355:
336:
317:
293:
220:
217:
214:
211:
210:
177:
131:
128:
125:
122:
121:
99:
92:
72:
43:on Knowledge's
40:
23:
22:
15:
12:
11:
5:
884:
882:
874:
873:
868:
863:
858:
853:
843:
842:
839:
838:
837:
836:
822:
808:Caleb Stanford
768:
765:
757:
756:
755:
745:Caleb Stanford
684:
683:
682:
681:
680:
659:
658:
656:
653:
632:
629:
626:
625:
598:
586:
585:
558:
546:
545:
518:
506:
505:
502:
501:
498:
497:
494:
493:
490:
489:
487:
486:
484:
483:
466:
458:
456:
455:
449:
439:
437:
436:
430:
420:
418:
417:
412:
404:
394:
392:
391:
385:
375:
373:
372:
366:
356:
354:
353:
347:
337:
335:
334:
328:
318:
316:
315:
310:
304:
294:
292:
291:
285:
273:
271:
270:
258:
257:
245:
244:
237:Low-importance
233:
227:
226:
224:
207:the discussion
193:
181:
180:
178:Low‑importance
172:
160:
159:
156:
155:
144:
138:
137:
135:
118:the discussion
105:
104:
88:
76:
75:
67:
55:
54:
48:
37:
24:
14:
13:
10:
9:
6:
4:
3:
2:
883:
872:
869:
867:
864:
862:
859:
857:
854:
852:
849:
848:
846:
835:
831:
827:
823:
819:
818:
817:
813:
809:
804:
803:
802:
801:
797:
793:
787:
785:
781:
777:
772:
766:
761:
754:
750:
746:
742:
741:
740:
739:
735:
731:
727:
721:
719:
714:
710:
706:
702:
698:
694:
690:
678:
675:
674:
673:
670:
667:
661:
660:
654:
652:
651:
647:
643:
638:
630:
623:
622:its talk page
618:
613:
609:
605:
604:
599:
592:
591:
583:
582:its talk page
578:
573:
569:
565:
564:
559:
552:
551:
543:
542:its talk page
538:
533:
529:
525:
524:
519:
512:
511:
479:
472:
468:
467:
465:
463:
459:
454:
451:
450:
448:
446:
445:
440:
435:
432:
431:
429:
427:
426:
421:
416:
413:
410:
406:
405:
403:
401:
400:
395:
390:
387:
386:
384:
382:
381:
376:
371:
368:
367:
365:
363:
362:
357:
352:
349:
348:
346:
344:
343:
338:
333:
330:
329:
327:
325:
324:
319:
314:
311:
309:
306:
305:
303:
301:
300:
295:
290:
287:
286:
284:
282:
281:
276:
275:
272:
268:
264:
263:
260:
259:
255:
251:
250:
246:
242:
238:
232:
229:
228:
225:
208:
204:
200:
199:
194:
191:
187:
186:
182:
176:
173:
170:
166:
153:
149:
143:
140:
139:
136:
119:
115:
111:
110:
102:
96:
91:
89:
86:
82:
81:
77:
71:
68:
65:
61:
56:
52:
46:
38:
34:
29:
28:
19:
788:
773:
770:
759:
722:
686:
676:
671:
665:
662:
637:modal logics
634:
601:
561:
521:
461:
460:
444:Unreferenced
442:
441:
423:
422:
397:
396:
378:
377:
359:
358:
340:
339:
321:
320:
297:
296:
278:
277:
236:
196:
148:Mid-priority
147:
107:
73:Mid‑priority
51:WikiProjects
631:Modal logic
617:its history
577:its history
537:its history
123:Mathematics
114:mathematics
70:Mathematics
845:Categories
606:page were
566:page were
526:page were
332:Computing
826:Felix QW
792:Felix QW
730:Felix QW
380:Maintain
323:Copyedit
821:places.
784:EXPTIME
776:FO(LFP)
767:SO(LFP)
361:Infobox
299:Cleanup
239:on the
150:on the
41:C-class
778:is to
608:merged
568:merged
528:merged
342:Expand
47:scale.
677:Merge
655:Merge
610:into
570:into
530:into
425:Stubs
399:Photo
256:with:
830:talk
812:talk
796:talk
749:talk
734:talk
711:and
699:and
646:talk
642:Spug
231:Low
142:Mid
847::
832:)
814:)
798:)
786:.
780:FO
751:)
736:)
695:,
648:)
640:--
481:}}
475:{{
828:(
810:(
794:(
747:(
732:(
644:(
624:.
584:.
544:.
464::
447::
428::
411:)
402::
383::
364::
345::
326::
302::
283::
243:.
154:.
53::
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
