127:. Usually the input is either a string (of bits or over an alphabet) and the elements of the logical structure represent positions of the string, or the input is a graph and the elements of the logical structure represent its vertices. The length of the input will be measured by the size of the respective structure. Whatever the structure is, we can assume that there are relations that can be tested, for example "
770:
such that the first-order quantifiers are universal and the quantifier-free part of the formula is in Krom form, which means that the first-order formula is a conjunction of disjunctions, and in each "disjunction" there are at most two variables. Every second-order Krom formula is equivalent to an
881:
Unlike most other characterisations of complexity classes, Fagin's theorem and its generalisation do not presuppose a total ordering on the structures. This is because existential second-order logic is itself sufficiently expressive to refer to the possible total orders on a structure using
61:. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific
203:
th letter of the string is 1." These relations are the predicates for the first-order logic system. We also have constants, which are special elements of the respective structure, for example if we want to check reachability in a graph, we will have to choose two constants
2364:
2209:
1297:
1111:. They are usually written in upper-case and with a natural number as exponent to indicate the order. Higher-order logic is the set of first-order formulae where we add quantification over higher-order variables; hence we will use the terms defined in the
798:
FO is the extension of first-order logic by a least fixed-point operator, which expresses the fixed-point of a monotone expression. This augments first-order logic with the ability to express recursion. The
Immerman–Vardi theorem, shown independently by
2010:
859:
Ronald Fagin's 1974 proof that the complexity class NP was characterised exactly by those classes of structures axiomatizable in existential second-order logic was the starting point of descriptive complexity theory.
920:
Second-order logic can be extended by a transitive closure operator in the same way as first-order logic, resulting in SO. The TC operator can now also take second-order variables as argument. SO characterises
1769:
215:
In descriptive complexity theory we often assume that there is a total order over the elements and that we can check equality between elements. This lets us consider elements as numbers: the element
1669:
2228:
2095:
1198:
870:. More precisely, we have the following generalisation of Fagin's theorem: The set of formulae in prenex normal form where existential and universal quantifiers of second order alternate
1354:
1388:
1582:
666:
905:, FO, is the extension of first-order logic with a partial fixed-point operator, which expresses the fixed-point of a formula if there is one and returns 'false' otherwise.
467:
382:
728:
First-order logic gains substantially in expressive power when it is augmented with an operator that computes the transitive closure of a binary relation. The resulting
1499:
1439:
1193:
324:
1039:
686:
283:
160:
2069:
2042:
706:
499:
414:
253:
1142:
197:
1882:
1525:
1109:
1005:
2089:
1856:
1836:
1809:
1789:
1479:
1459:
1408:
1317:
1162:
1079:
1059:
979:
863:
Since the complement of an existential formula is a universal formula, it follows immediately that co-NP is characterized by universal second-order logic.
1899:
509:
If we restrict ourselves to ordered structures with a successor relation and basic arithmetical predicates, then we get the following characterisations:
712:. First-order logic in a signature with arithmetical predicates characterises the restriction of the AC family of circuits to those constructible in
123:
When we use the logic formalism to describe a computational problem, the input is a finite structure, and the elements of that structure are the
817:
states that FO=FO on all structures if and only if FO=FO; hence if and only if P=PSPACE. This result has been extended to other fixpoints.
1674:
57:, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of
3037:
2534:
17:
2359:{\displaystyle {\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)})^{\Sigma _{j}^{\mathsf {P}}})}
1587:
744:
925:. Since ordering can be referenced in second-order logic, this characterisation does not presuppose ordered structures.
2730:
2204:{\displaystyle \exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Blue}{\mathsf {NP}}}}
1292:{\displaystyle \phi =\exists {\overline {X_{1}^{i}}}\forall {\overline {X_{2}^{i}}}\dots Q{\overline {X_{j}^{i}}}\psi }
2992:
2871:
2582:
2416:
2453:
Fagin, Ron (1974). "Generalized first-order spectra and polynomial-time recognizable sets". In Karp, Richard (ed.).
520:, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a
521:
3032:
34:
836:
form, which means that it is a big AND of OR, and in each "OR" every variable except possibly one are negated.
899:, can be characterised by augmenting first-order logic with a more expressive partial fixed-point operator.
810:
As of 2022, it is still open whether there is a natural logic characterising PTIME on unordered structures.
3042:
1838:
th is equivalent to a formula in prenex normal form, where we first write quantification over variable of
1322:
832:
such that the first-order quantifiers are all universal and the quantifier-free part of the formula is in
1359:
814:
1537:
825:
In the presence of a successor function, PTIME can also be characterised by second-order Horn formulae.
645:
2621:
902:
2713:
729:
100:
419:
2674:
2401:. Leibniz International Proceedings in Informatics (LIPIcs). Vol. 138. pp. 31:1–31:15.
829:
783:
767:
337:
3016:
2770:
2708:
642:
hierarchy. Indeed, there is a natural translation from FO's symbols to nodes of circuits, with
108:
104:
1484:
1413:
1167:
288:
846:
Those formulae can be transformed to prenex formulas in existential second-order Horn logic.
77:
2703:
Vardi, Moshe Y. (1982). "The complexity of relational query languages (Extended
Abstract)".
1018:
671:
262:
130:
2221:
2047:
2015:
867:
759:
On structures that have a successor function, NL can also be characterised by second-order
691:
472:
387:
226:
1121:
716:. First-order logic in a signature with only the order relation corresponds to the set of
173:
76:
expressible in it. The queries – when restricted to finite structures – correspond to the
8:
1861:
1504:
1088:
984:
124:
38:
567:
Universal second-order logic (excluding existential second-order quantification) yields
2877:
2736:
2510:
2483:
2213:
2074:
1841:
1821:
1794:
1774:
1464:
1444:
1393:
1302:
1147:
1064:
1044:
964:
958:
950:
717:
631:
610:
585:
539:
528:
96:
84:
73:
58:
2913:
2896:
2688:
2669:
2396:
2998:
2988:
2959:
2918:
2881:
2867:
2805:
2800:
2783:
2766:
2726:
2638:
2588:
2578:
2553:
2502:
2412:
954:
596:
550:
513:
2705:
Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82
2514:
2949:
2908:
2859:
2795:
2740:
2718:
2683:
2630:
2543:
2492:
2402:
2005:{\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}
946:
62:
42:
2092:
1112:
934:
733:
713:
639:
606:
578:
574:
561:
543:
334:
is 1. (We can replace addition and multiplication by ternary relations such that
92:
54:
50:
2856:[1989] Proceedings. Fourth Annual Symposium on Logic in Computer Science
2407:
2765:
Journal of the ACM archive, Volume 44, Issue 1 (January 1997), Pages: 30-56,
2762:
2754:
2217:
840:
748:
554:
532:
69:
2954:
2937:
2548:
2529:
1531:
766:
SO-Krom is the set of boolean queries definable with second-order formulae in
3026:
3002:
2963:
2922:
2851:
2809:
2642:
2592:
2557:
2506:
800:
737:
2863:
2758:
760:
88:
2722:
2497:
2478:
981:
th order and non-deterministic algorithms the time of which is bounded by
634:, first-order logic with arbitrary predicates can be shown to be equal to
95:
is precisely the set of languages expressible by sentences of existential
833:
804:
1893:
938:
614:
285:. Thanks to this we also may have the primitive predicate "bit", where
504:
2982:
2852:"Fixpoint extensions of first-order logic and datalog-like languages"
2616:
2572:
2634:
2479:"Fixpoint logics, relational machines, and computational complexity"
828:
SO-Horn is the set of boolean queries definable with SO formulae in
740:
to show that NL is closed under complement (i. e. that NL = co-NL).
2763:
Fixpoint logics, relational machines, and computational complexity
774:
SO-Krom characterises NL on structures with a successor function.
2784:"Capturing complexity classes by fragments of second-order logic"
1764:{\displaystyle \exp _{2}^{i+1}(x)=2^{2^{2^{2^{\dots ^{2^{x}}}}}}}
600:
961:
with higher-order quantifiers. There is a relation between the
115:. Many other classes were later characterized in such a manner.
2477:
Abiteboul, Serge; Vardi, Moshe Y.; Vianu, Victor (1997-01-15).
922:
909:
896:
589:
112:
546:, the problems solvable in nondeterministic logarithmic space.
2225:
1082:
787:
568:
46:
527:
First-order logic augmented with symmetric or deterministic
2948:(2). Essex, UK: Elsevier Science Publishers Ltd.: 197–214.
2542:(2). Essex, UK: Elsevier Science Publishers Ltd.: 197–214.
807:, shows that FO characterises PTIME on ordered structures.
2897:"On static logics, dynamic logics, and complexity classes"
895:
The class of all problems computable in polynomial space,
635:
557:, the problems solvable in deterministic polynomial time.
517:
2617:"Nondeterministic Space is Closed under Complementation"
1664:{\displaystyle \exp _{2}^{i+1}(x)=2^{\exp _{2}^{i}(x)}}
1144:
is the set of formulae with variables of order at most
2381:
2379:
1015:
We define higher-order variables. A variable of order
793:
2231:
2098:
2077:
2050:
2018:
1902:
1864:
1844:
1824:
1797:
1777:
1677:
1590:
1540:
1507:
1487:
1467:
1447:
1416:
1396:
1362:
1325:
1305:
1201:
1170:
1150:
1124:
1091:
1067:
1047:
1021:
987:
967:
866:
SO, unrestricted second-order logic, is equal to the
694:
674:
648:
475:
422:
390:
340:
291:
265:
229:
176:
133:
949:
of structures that can be recognized by formulas of
849:
743:
When restricting the transitive closure operator to
83:
The first main result of descriptive complexity was
2476:
2376:
505:
Overview of characterisations of complexity classes
2935:
2670:"Relational queries computable in polynomial time"
2527:
2358:
2203:
2083:
2063:
2036:
2004:
1876:
1850:
1830:
1803:
1783:
1763:
1663:
1576:
1519:
1493:
1473:
1453:
1433:
1402:
1382:
1348:
1311:
1291:
1187:
1156:
1136:
1103:
1073:
1053:
1033:
999:
973:
700:
680:
660:
493:
461:
408:
376:
318:
277:
247:
191:
154:
2394:
1887:
3024:
2936:Hella, Lauri; Turull-Torres, JosĂ© MarĂa (2006).
2528:Hella, Lauri; Turull-Torres, JosĂ© MarĂa (2006).
941:of elementary functions can be characterised by
890:
170:" (in case of the structure being a graph), or "
915:
2849:
2091:is a constant. A special case of this is that
1896:of elementary functions. To be more precise,
820:
754:
162:is true if and only if there is an edge from
2938:"Computing queries with higher-order logics"
2707:. New York, NY, USA: ACM. pp. 137–146.
2530:"Computing queries with higher-order logics"
747:, the resulting logic exactly characterises
603:, the problems solvable in exponential time.
592:, the problems solvable in polynomial space.
3017:Neil Immerman's descriptive complexity page
2858:. IEEE Comput. Soc. Press. pp. 71–79.
2395:Grädel, Erich; Schalthöfer, Svenja (2019).
723:
625:
2894:
2953:
2912:
2799:
2712:
2687:
2547:
2496:
2406:
843:on structures with a successor function.
535:, problems solvable in logarithmic space.
2980:
2667:
2614:
953:. Higher-order logic is an extension of
908:Partial fixed-point logic characterises
736:on ordered structures. This was used by
734:non-deterministic logarithmic space (NL)
99:; that is, second-order logic excluding
2570:
928:
771:existential second-order Krom formula.
14:
3025:
2781:
2345:
2273:
2270:
2267:
2264:
2261:
2238:
2235:
2194:
2191:
2154:
2151:
2148:
2145:
2142:
2121:
2118:
2107:
2104:
1942:
1939:
1936:
1933:
1930:
1909:
1906:
1195:is the subset of formulae of the form
878:th level of the polynomial hierarchy.
620:
560:Existential second-order logic yields
2702:
2654:
2652:
2452:
2258:
2188:
1858:th order and then a formula of order
1461:alternations of quantifiers of order
1115:article without defining them again.
2448:
2446:
2444:
2434:
2432:
2430:
2428:
1349:{\displaystyle Q{\overline {X^{i}}}}
2895:Harel, D.; Peleg, D. (1984-01-01).
2747:
1530:Using the standard notation of the
1410:with the same quantification. So HO
1383:{\displaystyle {\overline {X^{i}}}}
794:First-order least fixed-point logic
782:On ordered structures, first-order
24:
2649:
2335:
2099:
1577:{\displaystyle \exp _{2}^{0}(x)=x}
1488:
1233:
1208:
854:
777:
655:
649:
609:, the complexity class defined by
330:th bit of the binary expansion of
80:of traditional complexity theory.
25:
3054:
3010:
2850:Abiteboul, S.; Vianu, V. (1989).
2441:
2425:
1501:, followed by a formula of order
1390:is a tuple of variable of order
850:Non-deterministic polynomial time
661:{\displaystyle \forall ,\exists }
745:deterministic transitive closure
522:concurrent random access machine
3038:Computational complexity theory
2929:
2888:
2843:
2834:
2825:
2816:
2775:
2696:
2661:
2608:
35:computational complexity theory
2599:
2564:
2521:
2470:
2461:
2388:
2353:
2330:
2324:
2318:
2307:
2280:
2181:
2176:
2170:
2159:
2031:
2019:
1999:
1996:
1991:
1985:
1974:
1947:
1888:Relation to complexity classes
1813:
1708:
1702:
1656:
1650:
1621:
1615:
1565:
1559:
456:
438:
371:
353:
313:
301:
242:
230:
186:
180:
149:
137:
118:
13:
1:
2974:
2914:10.1016/S0019-9958(84)80023-6
2689:10.1016/s0019-9958(86)80029-8
1010:
891:Partial fixed point is PSPACE
91:in 1974. It established that
2942:Theoretical Computer Science
2801:10.1016/0304-3975(92)90149-A
2788:Theoretical Computer Science
2782:Grädel, Erich (1992-07-13).
2571:Robert., McNaughton (1971).
2535:Theoretical Computer Science
2398:Choiceless Logarithmic Space
1441:is the set of formulae with
1375:
1341:
1281:
1253:
1228:
916:Transitive closure is PSPACE
885:
714:alternating logarithmic time
588:(commutative or not) yields
462:{\displaystyle times(x,y,z)}
27:Branch of mathematical logic
7:
2408:10.4230/LIPICS.MFCS.2019.31
579:the polynomial hierarchy PH
377:{\displaystyle plus(x,y,z)}
199:is true if and only if the
10:
3059:
1061:and represents any set of
821:Second-order Horn formulae
755:Second-order Krom formulae
595:Second-order logic with a
584:Second-order logic with a
2955:10.1016/j.tcs.2006.01.009
2622:SIAM Journal on Computing
2549:10.1016/j.tcs.2006.01.009
2455:Complexity of Computation
1892:HO is equal to the class
903:Partial fixed-point logic
732:is known to characterise
638:, the first class in the
549:First-order logic with a
538:First-order logic with a
223:if and only if there are
2369:
1494:{\displaystyle \exists }
1434:{\displaystyle _{j}^{i}}
1188:{\displaystyle _{j}^{i}}
1007:levels of exponentials.
882:second-order variables.
730:transitive closure logic
724:Transitive closure logic
626:FO without any operators
319:{\displaystyle bit(x,k)}
101:universal quantification
2981:Immerman, Neil (1999).
2901:Information and Control
2864:10.1109/lics.1989.39160
2675:Information and Control
2668:Immerman, Neil (1986).
2658:Immerman 1999, p. 153–4
2615:Immerman, Neil (1988).
1818:Every formula of order
912:on ordered structures.
874:times characterise the
868:Polynomial hierarchy PH
839:This class is equal to
830:disjunctive normal form
815:Abiteboul–Vianu theorem
784:least fixed-point logic
768:conjunctive normal form
751:on ordered structures.
469:is true if and only if
384:is true if and only if
3033:Descriptive complexity
2984:Descriptive complexity
2360:
2205:
2085:
2065:
2038:
2006:
1878:
1852:
1832:
1805:
1785:
1765:
1665:
1578:
1521:
1495:
1475:
1455:
1435:
1404:
1384:
1350:
1313:
1293:
1189:
1158:
1138:
1105:
1075:
1055:
1035:
1034:{\displaystyle i>1}
1001:
975:
702:
682:
681:{\displaystyle \land }
662:
495:
463:
410:
378:
320:
279:
278:{\displaystyle y<x}
249:
219:represents the number
193:
156:
155:{\displaystyle E(x,y)}
78:computational problems
53:in them. For example,
49:needed to express the
31:Descriptive complexity
18:Descriptive complexity
3019:, including a diagram
2840:Immerman 1999, p. 181
2831:Immerman 1999, p. 121
2822:Immerman 1999, p. 115
2723:10.1145/800070.802186
2574:Counter-free automata
2498:10.1145/256292.256295
2467:Immerman 1999, p. 243
2438:Immerman 1999, p. 242
2361:
2206:
2086:
2066:
2064:{\displaystyle n^{c}}
2039:
2037:{\displaystyle (i-2)}
2012:, meaning a tower of
2007:
1879:
1853:
1833:
1806:
1786:
1766:
1666:
1579:
1522:
1496:
1476:
1456:
1436:
1405:
1385:
1351:
1314:
1294:
1190:
1159:
1139:
1106:
1085:of elements of order
1076:
1056:
1036:
1002:
976:
703:
701:{\displaystyle \lor }
683:
663:
577:logic corresponds to
496:
494:{\displaystyle x*y=z}
464:
411:
409:{\displaystyle x+y=z}
379:
321:
280:
250:
248:{\displaystyle (n-1)}
194:
157:
65:used to define them.
2605:Immerman 1999, p. 22
2385:Immerman 1999, p. 86
2229:
2222:polynomial hierarchy
2096:
2075:
2048:
2016:
1900:
1862:
1842:
1822:
1795:
1775:
1675:
1588:
1538:
1505:
1485:
1465:
1445:
1414:
1394:
1360:
1323:
1319:is a quantifier and
1303:
1199:
1168:
1148:
1137:{\displaystyle ^{i}}
1122:
1089:
1065:
1045:
1019:
985:
965:
929:Elementary functions
692:
672:
646:
473:
420:
388:
338:
326:is true if only the
289:
263:
227:
192:{\displaystyle P(n)}
174:
131:
3043:Finite model theory
2350:
2303:
2253:
2212:, which is exactly
2136:
1970:
1924:
1877:{\displaystyle i-1}
1698:
1646:
1611:
1555:
1520:{\displaystyle i-1}
1430:
1280:
1252:
1227:
1184:
1104:{\displaystyle i-1}
1000:{\displaystyle i-1}
718:star-free languages
621:Sub-polynomial time
125:domain of discourse
68:Specifically, each
41:that characterizes
39:finite model theory
2484:Journal of the ACM
2356:
2334:
2283:
2278:
2232:
2201:
2199:
2115:
2081:
2061:
2034:
2002:
1950:
1903:
1874:
1848:
1828:
1801:
1781:
1761:
1678:
1661:
1632:
1591:
1574:
1541:
1517:
1491:
1471:
1451:
1431:
1417:
1400:
1380:
1346:
1309:
1289:
1266:
1238:
1213:
1185:
1171:
1154:
1134:
1101:
1071:
1051:
1031:
997:
971:
959:second-order logic
951:higher-order logic
698:
678:
658:
632:circuit complexity
611:higher-order logic
586:transitive closure
540:transitive closure
529:transitive closure
516:defines the class
491:
459:
406:
374:
316:
275:
245:
189:
152:
97:second-order logic
72:produces a set of
59:second-order logic
43:complexity classes
2753:Serge Abiteboul,
2457:. pp. 43–73.
2084:{\displaystyle c}
1851:{\displaystyle i}
1831:{\displaystyle i}
1804:{\displaystyle 2}
1784:{\displaystyle i}
1481:, beginning with
1474:{\displaystyle i}
1454:{\displaystyle j}
1403:{\displaystyle i}
1378:
1344:
1312:{\displaystyle Q}
1284:
1256:
1231:
1157:{\displaystyle i}
1074:{\displaystyle k}
1054:{\displaystyle k}
974:{\displaystyle i}
955:first-order logic
749:logarithmic space
597:least fixed point
551:least fixed point
524:in constant time.
514:First-order logic
63:abstract machines
16:(Redirected from
3050:
3006:
2968:
2967:
2957:
2933:
2927:
2926:
2916:
2892:
2886:
2885:
2847:
2841:
2838:
2832:
2829:
2823:
2820:
2814:
2813:
2803:
2779:
2773:
2751:
2745:
2744:
2716:
2700:
2694:
2693:
2691:
2665:
2659:
2656:
2647:
2646:
2612:
2606:
2603:
2597:
2596:
2577:. M.I.T. Press.
2568:
2562:
2561:
2551:
2525:
2519:
2518:
2500:
2474:
2468:
2465:
2459:
2458:
2450:
2439:
2436:
2423:
2422:
2410:
2392:
2386:
2383:
2365:
2363:
2362:
2357:
2352:
2351:
2349:
2348:
2342:
2328:
2327:
2302:
2291:
2279:
2277:
2276:
2252:
2247:
2242:
2241:
2210:
2208:
2207:
2202:
2200:
2198:
2197:
2180:
2179:
2158:
2157:
2135:
2130:
2125:
2124:
2111:
2110:
2090:
2088:
2087:
2082:
2070:
2068:
2067:
2062:
2060:
2059:
2044:2s, ending with
2043:
2041:
2040:
2035:
2011:
2009:
2008:
2003:
1995:
1994:
1969:
1958:
1946:
1945:
1923:
1918:
1913:
1912:
1884:in normal form.
1883:
1881:
1880:
1875:
1857:
1855:
1854:
1849:
1837:
1835:
1834:
1829:
1810:
1808:
1807:
1802:
1790:
1788:
1787:
1782:
1770:
1768:
1767:
1762:
1760:
1759:
1758:
1757:
1756:
1755:
1754:
1753:
1752:
1751:
1750:
1749:
1697:
1686:
1670:
1668:
1667:
1662:
1660:
1659:
1645:
1640:
1610:
1599:
1583:
1581:
1580:
1575:
1554:
1549:
1526:
1524:
1523:
1518:
1500:
1498:
1497:
1492:
1480:
1478:
1477:
1472:
1460:
1458:
1457:
1452:
1440:
1438:
1437:
1432:
1429:
1424:
1409:
1407:
1406:
1401:
1389:
1387:
1386:
1381:
1379:
1374:
1373:
1364:
1355:
1353:
1352:
1347:
1345:
1340:
1339:
1330:
1318:
1316:
1315:
1310:
1298:
1296:
1295:
1290:
1285:
1279:
1274:
1265:
1257:
1251:
1246:
1237:
1232:
1226:
1221:
1212:
1194:
1192:
1191:
1186:
1183:
1178:
1163:
1161:
1160:
1155:
1143:
1141:
1140:
1135:
1133:
1132:
1110:
1108:
1107:
1102:
1080:
1078:
1077:
1072:
1060:
1058:
1057:
1052:
1040:
1038:
1037:
1032:
1006:
1004:
1003:
998:
980:
978:
977:
972:
947:complexity class
711:
707:
705:
704:
699:
687:
685:
684:
679:
667:
665:
664:
659:
542:operator yields
531:operators yield
500:
498:
497:
492:
468:
466:
465:
460:
415:
413:
412:
407:
383:
381:
380:
375:
333:
329:
325:
323:
322:
317:
284:
282:
281:
276:
258:
254:
252:
251:
246:
222:
218:
202:
198:
196:
195:
190:
169:
165:
161:
159:
158:
153:
21:
3058:
3057:
3053:
3052:
3051:
3049:
3048:
3047:
3023:
3022:
3013:
2995:
2977:
2972:
2971:
2934:
2930:
2893:
2889:
2874:
2848:
2844:
2839:
2835:
2830:
2826:
2821:
2817:
2780:
2776:
2752:
2748:
2733:
2714:10.1.1.331.6045
2701:
2697:
2682:(1–3): 86–104.
2666:
2662:
2657:
2650:
2635:10.1137/0217058
2613:
2609:
2604:
2600:
2585:
2569:
2565:
2526:
2522:
2475:
2471:
2466:
2462:
2451:
2442:
2437:
2426:
2419:
2393:
2389:
2384:
2377:
2372:
2344:
2343:
2338:
2333:
2329:
2314:
2310:
2292:
2287:
2260:
2259:
2257:
2248:
2243:
2234:
2233:
2230:
2227:
2226:
2218:oracle machines
2214:Fagin's theorem
2190:
2189:
2187:
2166:
2162:
2141:
2140:
2131:
2126:
2117:
2116:
2103:
2102:
2097:
2094:
2093:
2076:
2073:
2072:
2055:
2051:
2049:
2046:
2045:
2017:
2014:
2013:
1981:
1977:
1959:
1954:
1929:
1928:
1919:
1914:
1905:
1904:
1901:
1898:
1897:
1890:
1863:
1860:
1859:
1843:
1840:
1839:
1823:
1820:
1819:
1816:
1796:
1793:
1792:
1776:
1773:
1772:
1745:
1741:
1740:
1737:
1733:
1729:
1728:
1724:
1723:
1719:
1718:
1714:
1687:
1682:
1676:
1673:
1672:
1641:
1636:
1631:
1627:
1600:
1595:
1589:
1586:
1585:
1550:
1545:
1539:
1536:
1535:
1506:
1503:
1502:
1486:
1483:
1482:
1466:
1463:
1462:
1446:
1443:
1442:
1425:
1420:
1415:
1412:
1411:
1395:
1392:
1391:
1369:
1365:
1363:
1361:
1358:
1357:
1335:
1331:
1329:
1324:
1321:
1320:
1304:
1301:
1300:
1275:
1270:
1264:
1247:
1242:
1236:
1222:
1217:
1211:
1200:
1197:
1196:
1179:
1174:
1169:
1166:
1165:
1149:
1146:
1145:
1128:
1125:
1123:
1120:
1119:
1090:
1087:
1086:
1066:
1063:
1062:
1046:
1043:
1042:
1020:
1017:
1016:
1013:
986:
983:
982:
966:
963:
962:
935:time complexity
931:
918:
893:
888:
857:
855:Fagin's theorem
852:
823:
796:
780:
778:Polynomial time
757:
726:
709:
693:
690:
689:
673:
670:
669:
647:
644:
643:
628:
623:
599:operator gives
553:operator gives
507:
474:
471:
470:
421:
418:
417:
389:
386:
385:
339:
336:
335:
331:
327:
290:
287:
286:
264:
261:
260:
256:
228:
225:
224:
220:
216:
200:
175:
172:
171:
167:
163:
132:
129:
128:
121:
85:Fagin's theorem
45:by the type of
33:is a branch of
28:
23:
22:
15:
12:
11:
5:
3056:
3046:
3045:
3040:
3035:
3021:
3020:
3012:
3011:External links
3009:
3008:
3007:
2993:
2976:
2973:
2970:
2969:
2928:
2887:
2872:
2842:
2833:
2824:
2815:
2774:
2755:Moshe Y. Vardi
2746:
2732:978-0897910705
2731:
2695:
2660:
2648:
2629:(5): 935–938.
2607:
2598:
2583:
2563:
2520:
2469:
2460:
2440:
2424:
2417:
2387:
2374:
2373:
2371:
2368:
2355:
2347:
2341:
2337:
2332:
2326:
2323:
2320:
2317:
2313:
2309:
2306:
2301:
2298:
2295:
2290:
2286:
2282:
2275:
2272:
2269:
2266:
2263:
2256:
2251:
2246:
2240:
2237:
2196:
2193:
2186:
2183:
2178:
2175:
2172:
2169:
2165:
2161:
2156:
2153:
2150:
2147:
2144:
2139:
2134:
2129:
2123:
2120:
2114:
2109:
2106:
2101:
2080:
2058:
2054:
2033:
2030:
2027:
2024:
2021:
2001:
1998:
1993:
1990:
1987:
1984:
1980:
1976:
1973:
1968:
1965:
1962:
1957:
1953:
1949:
1944:
1941:
1938:
1935:
1932:
1927:
1922:
1917:
1911:
1908:
1889:
1886:
1873:
1870:
1867:
1847:
1827:
1815:
1812:
1800:
1780:
1748:
1744:
1739:
1736:
1732:
1727:
1722:
1717:
1713:
1710:
1707:
1704:
1701:
1696:
1693:
1690:
1685:
1681:
1658:
1655:
1652:
1649:
1644:
1639:
1635:
1630:
1626:
1623:
1620:
1617:
1614:
1609:
1606:
1603:
1598:
1594:
1573:
1570:
1567:
1564:
1561:
1558:
1553:
1548:
1544:
1516:
1513:
1510:
1490:
1470:
1450:
1428:
1423:
1419:
1399:
1377:
1372:
1368:
1343:
1338:
1334:
1328:
1308:
1288:
1283:
1278:
1273:
1269:
1263:
1260:
1255:
1250:
1245:
1241:
1235:
1230:
1225:
1220:
1216:
1210:
1207:
1204:
1182:
1177:
1173:
1153:
1131:
1127:
1100:
1097:
1094:
1070:
1050:
1030:
1027:
1024:
1012:
1009:
996:
993:
990:
970:
930:
927:
917:
914:
892:
889:
887:
884:
856:
853:
851:
848:
822:
819:
795:
792:
779:
776:
756:
753:
725:
722:
697:
677:
657:
654:
651:
627:
624:
622:
619:
618:
617:
613:, is equal to
604:
593:
582:
572:
565:
558:
547:
536:
525:
506:
503:
490:
487:
484:
481:
478:
458:
455:
452:
449:
446:
443:
440:
437:
434:
431:
428:
425:
405:
402:
399:
396:
393:
373:
370:
367:
364:
361:
358:
355:
352:
349:
346:
343:
315:
312:
309:
306:
303:
300:
297:
294:
274:
271:
268:
244:
241:
238:
235:
232:
188:
185:
182:
179:
151:
148:
145:
142:
139:
136:
120:
117:
70:logical system
26:
9:
6:
4:
3:
2:
3055:
3044:
3041:
3039:
3036:
3034:
3031:
3030:
3028:
3018:
3015:
3014:
3004:
3000:
2996:
2994:0-387-98600-6
2990:
2986:
2985:
2979:
2978:
2965:
2961:
2956:
2951:
2947:
2943:
2939:
2932:
2924:
2920:
2915:
2910:
2907:(1): 86–102.
2906:
2902:
2898:
2891:
2883:
2879:
2875:
2873:0-8186-1954-6
2869:
2865:
2861:
2857:
2853:
2846:
2837:
2828:
2819:
2811:
2807:
2802:
2797:
2793:
2789:
2785:
2778:
2772:
2768:
2764:
2760:
2756:
2750:
2742:
2738:
2734:
2728:
2724:
2720:
2715:
2710:
2706:
2699:
2690:
2685:
2681:
2677:
2676:
2671:
2664:
2655:
2653:
2644:
2640:
2636:
2632:
2628:
2624:
2623:
2618:
2611:
2602:
2594:
2590:
2586:
2584:0-262-13076-9
2580:
2576:
2575:
2567:
2559:
2555:
2550:
2545:
2541:
2537:
2536:
2531:
2524:
2516:
2512:
2508:
2504:
2499:
2494:
2490:
2486:
2485:
2480:
2473:
2464:
2456:
2449:
2447:
2445:
2435:
2433:
2431:
2429:
2420:
2418:9783959771177
2414:
2409:
2404:
2400:
2399:
2391:
2382:
2380:
2375:
2367:
2366:
2339:
2321:
2315:
2311:
2304:
2299:
2296:
2293:
2288:
2284:
2254:
2249:
2244:
2223:
2219:
2215:
2211:
2184:
2173:
2167:
2163:
2137:
2132:
2127:
2112:
2078:
2056:
2052:
2028:
2025:
2022:
1988:
1982:
1978:
1971:
1966:
1963:
1960:
1955:
1951:
1925:
1920:
1915:
1895:
1885:
1871:
1868:
1865:
1845:
1825:
1811:
1798:
1778:
1746:
1742:
1738:
1734:
1730:
1725:
1720:
1715:
1711:
1705:
1699:
1694:
1691:
1688:
1683:
1679:
1653:
1647:
1642:
1637:
1633:
1628:
1624:
1618:
1612:
1607:
1604:
1601:
1596:
1592:
1571:
1568:
1562:
1556:
1551:
1546:
1542:
1533:
1528:
1514:
1511:
1508:
1468:
1448:
1426:
1421:
1418:
1397:
1370:
1366:
1336:
1332:
1326:
1306:
1286:
1276:
1271:
1267:
1261:
1258:
1248:
1243:
1239:
1223:
1218:
1214:
1205:
1202:
1180:
1175:
1172:
1151:
1129:
1126:
1116:
1114:
1098:
1095:
1092:
1084:
1068:
1048:
1041:has an arity
1028:
1025:
1022:
1008:
994:
991:
988:
968:
960:
956:
952:
948:
944:
940:
936:
926:
924:
913:
911:
906:
904:
900:
898:
883:
879:
877:
873:
869:
864:
861:
847:
844:
842:
837:
835:
831:
826:
818:
816:
811:
808:
806:
802:
791:
789:
785:
775:
772:
769:
764:
762:
761:Krom formulae
752:
750:
746:
741:
739:
735:
731:
721:
719:
715:
695:
675:
652:
641:
637:
633:
616:
612:
608:
605:
602:
598:
594:
591:
587:
583:
580:
576:
573:
570:
566:
563:
559:
556:
552:
548:
545:
541:
537:
534:
530:
526:
523:
519:
515:
512:
511:
510:
502:
488:
485:
482:
479:
476:
453:
450:
447:
444:
441:
435:
432:
429:
426:
423:
403:
400:
397:
394:
391:
368:
365:
362:
359:
356:
350:
347:
344:
341:
310:
307:
304:
298:
295:
292:
272:
269:
266:
239:
236:
233:
213:
211:
207:
183:
177:
146:
143:
140:
134:
126:
116:
114:
110:
106:
102:
98:
94:
90:
86:
81:
79:
75:
71:
66:
64:
60:
56:
52:
48:
44:
40:
36:
32:
19:
2987:. Springer.
2983:
2945:
2941:
2931:
2904:
2900:
2890:
2855:
2845:
2836:
2827:
2818:
2794:(1): 35–57.
2791:
2787:
2777:
2759:Victor Vianu
2749:
2704:
2698:
2679:
2673:
2663:
2626:
2620:
2610:
2601:
2573:
2566:
2539:
2533:
2523:
2491:(1): 30–56.
2488:
2482:
2472:
2463:
2454:
2397:
2390:
1891:
1817:
1529:
1117:
1014:
942:
932:
919:
907:
901:
894:
880:
875:
871:
865:
862:
858:
845:
838:
827:
824:
812:
809:
797:
781:
773:
765:
758:
742:
727:
629:
575:Second-order
508:
214:
212:(terminal).
209:
208:(start) and
205:
122:
89:Ronald Fagin
82:
67:
30:
29:
1814:Normal form
1356:means that
119:The setting
87:, shown by
3027:Categories
2975:References
1894:ELEMENTARY
1011:Definition
939:ELEMENTARY
615:ELEMENTARY
3003:901297152
2964:0304-3975
2923:0019-9958
2882:206437693
2810:0304-3975
2771:0004-5411
2709:CiteSeerX
2643:0097-5397
2593:651199926
2558:0304-3975
2507:0004-5411
2336:Σ
2305:
2297:−
2100:∃
2026:−
1972:
1964:−
1869:−
1735:…
1700:
1648:
1613:
1557:
1532:tetration
1512:−
1489:∃
1376:¯
1342:¯
1287:ψ
1282:¯
1259:…
1254:¯
1234:∀
1229:¯
1209:∃
1203:ϕ
1096:−
992:−
886:Beyond NP
786:captures
696:∨
676:∧
656:∃
650:∀
480:∗
255:elements
237:−
109:functions
105:relations
51:languages
2515:11338470
2216:. Using
2071:, where
1299:, where
801:Immerman
738:Immerman
708:of size
2741:7869248
2220:in the
601:EXPTIME
113:subsets
74:queries
37:and of
3001:
2991:
2962:
2921:
2880:
2870:
2808:
2769:
2739:
2729:
2711:
2641:
2591:
2581:
2556:
2513:
2505:
2415:
1791:times
1083:tuples
945:, the
937:class
923:PSPACE
910:PSPACE
897:PSPACE
668:being
590:PSPACE
111:, and
2878:S2CID
2737:S2CID
2511:S2CID
2370:Notes
1771:with
805:Vardi
788:PTIME
569:co-NP
259:with
103:over
47:logic
2999:OCLC
2989:ISBN
2960:ISSN
2919:ISSN
2868:ISBN
2806:ISSN
2767:ISSN
2727:ISBN
2639:ISSN
2589:OCLC
2579:ISBN
2554:ISSN
2503:ISSN
2413:ISBN
1584:and
1164:. HO
1026:>
957:and
933:The
834:Horn
813:The
803:and
688:and
416:and
270:<
2950:doi
2946:355
2909:doi
2860:doi
2796:doi
2792:101
2719:doi
2684:doi
2631:doi
2544:doi
2540:355
2493:doi
2403:doi
2285:exp
1952:exp
1680:exp
1634:exp
1593:exp
1543:exp
630:In
501:).
166:to
3029::
2997:.
2958:.
2944:.
2940:.
2917:.
2905:60
2903:.
2899:.
2876:.
2866:.
2854:.
2804:.
2790:.
2786:.
2761::
2757:,
2735:.
2725:.
2717:.
2680:68
2678:.
2672:.
2651:^
2637:.
2627:17
2625:.
2619:.
2587:.
2552:.
2538:.
2532:.
2509:.
2501:.
2489:44
2487:.
2481:.
2443:^
2427:^
2411:.
2378:^
2224:,
1671:.
1534:,
1527:.
1118:HO
1113:FO
943:HO
790::
763:.
720:.
640:AC
636:AC
607:HO
562:NP
544:NL
518:AC
107:,
93:NP
55:PH
3005:.
2966:.
2952::
2925:.
2911::
2884:.
2862::
2812:.
2798::
2743:.
2721::
2692:.
2686::
2645:.
2633::
2595:.
2560:.
2546::
2517:.
2495::
2421:.
2405::
2354:)
2346:P
2340:j
2331:)
2325:)
2322:1
2319:(
2316:O
2312:n
2308:(
2300:2
2294:i
2289:2
2281:(
2274:E
2271:M
2268:I
2265:T
2262:N
2255:=
2250:i
2245:j
2239:O
2236:H
2195:P
2192:N
2185:=
2182:)
2177:)
2174:1
2171:(
2168:O
2164:n
2160:(
2155:E
2152:M
2149:I
2146:T
2143:N
2138:=
2133:2
2128:0
2122:O
2119:H
2113:=
2108:O
2105:S
2079:c
2057:c
2053:n
2032:)
2029:2
2023:i
2020:(
2000:)
1997:)
1992:)
1989:1
1986:(
1983:O
1979:n
1975:(
1967:2
1961:i
1956:2
1948:(
1943:E
1940:M
1937:I
1934:T
1931:N
1926:=
1921:i
1916:0
1910:O
1907:H
1872:1
1866:i
1846:i
1826:i
1799:2
1779:i
1747:x
1743:2
1731:2
1726:2
1721:2
1716:2
1712:=
1709:)
1706:x
1703:(
1695:1
1692:+
1689:i
1684:2
1657:)
1654:x
1651:(
1643:i
1638:2
1629:2
1625:=
1622:)
1619:x
1616:(
1608:1
1605:+
1602:i
1597:2
1572:x
1569:=
1566:)
1563:x
1560:(
1552:0
1547:2
1515:1
1509:i
1469:i
1449:j
1427:i
1422:j
1398:i
1371:i
1367:X
1337:i
1333:X
1327:Q
1307:Q
1277:i
1272:j
1268:X
1262:Q
1249:i
1244:2
1240:X
1224:i
1219:1
1215:X
1206:=
1181:i
1176:j
1152:i
1130:i
1099:1
1093:i
1081:-
1069:k
1049:k
1029:1
1023:i
995:1
989:i
969:i
876:k
872:k
841:P
710:n
653:,
581:.
571:.
564:.
555:P
533:L
489:z
486:=
483:y
477:x
457:)
454:z
451:,
448:y
445:,
442:x
439:(
436:s
433:e
430:m
427:i
424:t
404:z
401:=
398:y
395:+
392:x
372:)
369:z
366:,
363:y
360:,
357:x
354:(
351:s
348:u
345:l
342:p
332:x
328:k
314:)
311:k
308:,
305:x
302:(
299:t
296:i
293:b
273:x
267:y
257:y
243:)
240:1
234:n
231:(
221:n
217:x
210:t
206:s
201:n
187:)
184:n
181:(
178:P
168:y
164:x
150:)
147:y
144:,
141:x
138:(
135:E
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.