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