Editing Descriptive complexity theory (section)

==Overview of characterisations of complexity classes==
If we restrict ourselves to ordered structures with a successor relation and basic arithmetical predicates, then we get the following characterisations:
* [[First-order logic]] defines the class [[AC0|AC<sup>0</sup>]], the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a [[concurrent random access machine]] in constant time.<ref name="Immerman 1999, p. 86">Immerman 1999, p. 86</ref>
* First-order logic augmented with symmetric or deterministic [[transitive closure]] operators yield [[L (complexity)|L]], problems solvable in logarithmic space.<ref>{{Cite book|last1=Grädel|first1=Erich|last2=Schalthöfer|first2=Svenja|date=2019|title=Choiceless Logarithmic Space|series=Leibniz International Proceedings in Informatics (LIPIcs)|volume=138|url=http://drops.dagstuhl.de/opus/volltexte/2019/10975/|language=en|pages=31:1–31:15|doi=10.4230/LIPICS.MFCS.2019.31|doi-access=free |isbn=9783959771177}}</ref>
* First-order logic with a [[transitive closure]] operator yields [[NL (complexity)|NL]], the problems solvable in nondeterministic logarithmic space.<ref name=":0">Immerman 1999, p. 242</ref>
* First-order logic with a [[least fixed point]] operator gives [[P (complexity)|P]], the problems solvable in deterministic polynomial time.<ref name=":0" />
* Existential second-order logic yields [[NP (complexity)|NP]].<ref name=":0" />
* Universal second-order logic (excluding existential second-order quantification) yields [[co-NP]].<ref name=":1">{{Cite book|last=Fagin|first=Ron|title=Complexity of Computation|year=1974|editor-last=Karp|editor-first=Richard|pages=43{{mdash}}73|chapter=Generalized first-order spectra and polynomial-time recognizable sets}}</ref>
* [[SO (complexity)|Second-order]] logic corresponds to [[PH (complexity)|the polynomial hierarchy PH]].<ref name=":0" />
* Second-order logic with a [[transitive closure]] (commutative or not) yields [[PSPACE]], the problems solvable in polynomial space.<ref>Immerman 1999, p. 243</ref>
* Second-order logic with a [[least fixed point]] operator gives [[EXPTIME]], the problems solvable in exponential time.<ref>{{Cite journal|last1=Abiteboul|first1=Serge|last2=Vardi|first2=Moshe Y.|last3=Vianu|first3=Victor|date=1997-01-15|title=Fixpoint logics, relational machines, and computational complexity|journal=[[Journal of the ACM]]|language=en|volume=44|issue=1|pages=30–56|doi=10.1145/256292.256295|s2cid=11338470|issn=0004-5411|doi-access=free}}</ref> 
* [[HO (complexity)|HO]], the complexity class defined by [[higher-order logic]], is equal to [[ELEMENTARY]]<ref>{{Cite journal| first1 = Lauri|last1= Hella|first2 = José María|last2 = Turull-Torres | title =Computing queries with higher-order logics | journal =[[Theoretical Computer Science (journal)|Theoretical Computer Science]] | volume = 355 | issue = 2 | year = 2006 | pages = 197–214   | issn =0304-3975 | publisher =Elsevier Science Publishers Ltd. | place =  Essex, UK | doi=10.1016/j.tcs.2006.01.009| doi-access = free }}</ref>