Editing Descriptive complexity theory

{{Short description|Branch of mathematical logic}}

'''Descriptive complexity''' is a branch of [[computational complexity theory]] and of [[finite model theory]] that characterizes [[complexity class]]es by the type of [[logic]] needed to express the [[formal language|language]]s in them. For example, [[PH (complexity)|PH]], the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of [[second-order logic]]. 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 [[abstract machine]]s used to define them.

Specifically, each [[logical system]] produces a set of [[query (complexity)|queries]] expressible in it. The queries – when restricted to finite structures – correspond to the [[computational problem]]s of traditional complexity theory.

The first main result of descriptive complexity was [[Fagin's theorem]], shown by [[Ronald Fagin]] in 1974. It established that [[NP (complexity)|NP]] is precisely the set of languages expressible by sentences of existential [[second-order logic]]; that is, second-order logic excluding [[universal quantification]] over [[relation (mathematics)|relation]]s, [[function (mathematics)|function]]s, and [[subset]]s. Many other classes were later characterized in such a manner.

==The setting==

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 [[domain of discourse]]. 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 "<math>E(x,y)</math> is true if and only if there is an edge from {{mvar|x}} to {{mvar|y}}" (in case of the structure being a graph), or "<math>P(n)</math> is true if and only if the {{mvar|n}}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 ''s'' (start) and ''t'' (terminal).

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 {{mvar|x}} represents the number {{mvar|n}} if and only if there are <math>(n-1)</math> elements {{mvar|y}} with <math>y<x</math>. Thanks to this we also may have the primitive predicate "bit", where <math>bit(x,k)</math> is true if only the {{mvar|k}}th bit of the binary expansion of {{mvar|x}} is 1. (We can replace addition and multiplication by ternary relations such that <math>plus(x,y,z)</math> is true if and only if <math>x+y=z</math> and <math>times(x,y,z)</math> is true if and only if <math>x*y=z</math>).

==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>

== Sub-polynomial time ==

=== FO without any operators ===

In [[circuit complexity]], first-order logic with arbitrary predicates can be shown to be equal to [[AC0|AC<sup>0</sup>]], the first class in the [[AC (complexity)|AC]] hierarchy. Indeed, there is a natural translation from FO's symbols to nodes of circuits, with <math>\forall, \exists</math> being <math>\land</math> and <math>\lor</math> of size {{mvar|n}}. First-order logic in a signature with arithmetical predicates characterises the restriction of  the AC<sup>0</sup> family of circuits to those constructible in [[LH (complexity)|alternating logarithmic time]].<ref name="Immerman 1999, p. 86"/> First-order logic in a signature with only the order relation corresponds to the set of [[star-free language]]s.<ref>{{Cite book|last=Robert.|first=McNaughton|url=http://worldcat.org/oclc/651199926|title=Counter-free automata|date=1971|publisher=M.I.T. Press|isbn=0-262-13076-9|oclc=651199926}}</ref><ref>Immerman 1999, p. 22</ref>

=== Transitive closure logic ===
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 [[transitive closure logic]] is known to characterise [[NL (complexity)|non-deterministic logarithmic space (NL)]] on ordered structures. This was used by [[Neil Immerman|Immerman]] to show that NL is closed under complement (i. e. that NL = co-NL).<ref>{{Cite journal|last=Immerman|first=Neil|date=1988|title=Nondeterministic Space is Closed under Complementation|url=http://dx.doi.org/10.1137/0217058|journal=[[SIAM Journal on Computing]]|volume=17|issue=5|pages=935–938|doi=10.1137/0217058|issn=0097-5397}}</ref>

When restricting the transitive closure operator to [[Fixed-point logic#Deterministic transitive closure logic|deterministic transitive closure]], the resulting logic exactly characterises [[L (complexity)|logarithmic space]] on ordered structures.

=== Second-order Krom formulae ===
On structures that have a successor function, NL can also be characterised by second-order [[Krom formula]]e.

SO-Krom is the set of Boolean queries definable with second-order formulae in [[conjunctive normal form]] 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 existential second-order Krom formula.

SO-Krom characterises NL on structures with a successor function.<ref name=":2">Immerman 1999, p. 153{{Ndash}}4</ref>

== Polynomial time ==
On ordered structures, first-order [[least fixed-point logic]] captures [[PTIME]]:

=== First-order least fixed-point logic ===
FO[LFP] 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 [[Neil Immerman|Immerman]] and [[Moshe Vardi|Vardi]], shows that FO[LFP] characterises PTIME on ordered structures.<ref>{{Cite journal|last=Immerman|first=Neil|year=1986|title=Relational queries computable in polynomial time|journal=[[Information and Control]]|language=en|volume=68|issue=1–3|pages=86–104|doi=10.1016/s0019-9958(86)80029-8|doi-access=free}}</ref><ref>{{Cite book|last=Vardi|first=Moshe Y.|chapter=The complexity of relational query languages (Extended Abstract) |title=Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82|date=1982|publisher=ACM|isbn=978-0897910705|location=New York, NY, USA|pages=137–146|citeseerx=10.1.1.331.6045|doi=10.1145/800070.802186|s2cid=7869248}}</ref>

As of 2022, it is still open whether there is a natural logic characterising PTIME on unordered structures.

The [[Abiteboul–Vianu theorem]] states that FO[LFP]=FO[PFP] on all structures if and only if FO[LFP]=FO[PFP]; hence if and only if P=PSPACE. This result has been extended to other fixpoints.<ref name="avv">Serge Abiteboul, [[Moshe Y. Vardi]], [[Victor Vianu]]: [http://portal.acm.org/citation.cfm?id=256295 Fixpoint logics, relational machines, and computational complexity] Journal of the ACM archive, Volume 44,  Issue 1  (January 1997), Pages: 30-56, {{ISSN|0004-5411}}</ref>

=== Second-order Horn formulae ===
In the presence of a successor function, PTIME can also be characterised by second-order Horn formulae.

SO-Horn is the set of Boolean queries definable with SO formulae in [[disjunctive normal form]] such that the first-order quantifiers are all universal and the quantifier-free part of the formula is in [[Horn clause|Horn]] form, which means that it is a big AND of OR, and in each "OR" every variable except possibly one are negated.

This class is equal to [[P (complexity)|P]] on structures with a successor function.<ref>{{Cite journal|last=Grädel|first=Erich|date=1992-07-13|title=Capturing complexity classes by fragments of second-order logic|journal=Theoretical Computer Science|language=en|volume=101|issue=1|pages=35–57|doi=10.1016/0304-3975(92)90149-A|issn=0304-3975|doi-access=free}}</ref>

Those formulae can be transformed to prenex formulas in existential second-order Horn logic.<ref name=":2" />

== Non-deterministic polynomial time ==

=== Fagin's theorem ===
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.<ref name=":1" /><ref>Immerman 1999, p. 115</ref>

Since the complement of an existential formula is a universal formula, it follows immediately that co-NP is characterized by universal second-order logic.<ref name=":1" />

SO, unrestricted second-order logic, is equal to the [[Polynomial hierarchy|Polynomial hierarchy PH]]. 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 ''k'' times characterise the ''k''th level of the polynomial hierarchy.<ref>Immerman 1999, p. 121</ref>

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 second-order variables.<ref>Immerman 1999, p. 181</ref>

== Beyond NP ==

=== Partial fixed point is PSPACE ===
The class of all problems computable in polynomial space, [[PSPACE]], can be characterised by augmenting first-order logic with a more expressive partial fixed-point operator.

[[Partial fixed-point logic]], FO[PFP], 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.

Partial fixed-point logic characterises [[PSPACE]] on ordered structures.<ref>{{Cite book|last1=Abiteboul|first1=S.|last2=Vianu|first2=V.|title=&#91;1989&#93; Proceedings. Fourth Annual Symposium on Logic in Computer Science |chapter=Fixpoint extensions of first-order logic and datalog-like languages |chapter-url=http://dx.doi.org/10.1109/lics.1989.39160|year=1989|pages=71–79|publisher=IEEE Comput. Soc. Press|doi=10.1109/lics.1989.39160|isbn=0-8186-1954-6|s2cid=206437693}}</ref>

=== Transitive closure is PSPACE ===
Second-order logic can be extended by a transitive closure operator in the same way as first-order logic, resulting in SO[TC]. The TC operator can now also take second-order variables as argument. SO[TC] characterises [[PSPACE]]. Since ordering can be referenced in second-order logic, this characterisation does not presuppose ordered structures.<ref>{{Cite journal|last1=Harel|first1=D.|last2=Peleg|first2=D.|date=1984-01-01|title=On static logics, dynamic logics, and complexity classes|journal=Information and Control|language=en|volume=60|issue=1|pages=86–102|doi=10.1016/S0019-9958(84)80023-6|issn=0019-9958|doi-access=free}}</ref>

==Elementary functions==
The [[time complexity]] class [[ELEMENTARY]] of elementary functions can be characterised by '''HO''', the [[complexity class]] of structures that can be recognized by formulas of [[higher-order logic]]. Higher-order logic is an extension of [[first-order logic]] and [[second-order logic]] with higher-order quantifiers.  There is a relation between the <math>i</math>th order and non-deterministic algorithms the time of which is bounded by <math>i-1</math> levels of exponentials.<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 | 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>

=== Definition ===
We define higher-order variables. A variable of order <math>i>1</math> has an arity <math>k</math> and represents any set of <math>k</math>-[[tuple]]s of elements of order <math>i-1</math>. 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 [[FO (complexity)|FO]] article without defining them again.

HO<math>^i</math> is the set of formulae with variables of order at most <math>i</math>. HO<math>^i_j</math> is the subset of formulae of the form <math>\phi=\exists \overline{X^i_1}\forall\overline{X_2^i}\dots Q \overline{X_j^i}\psi</math>, where <math>Q</math> is a quantifier and <math>Q \overline{X^i}</math> means that <math>\overline{X^i}</math> is  a tuple of variable of order <math>i</math> with the same quantification. So HO<math>^i_j</math> is the set of formulae with <math>j</math> alternations of quantifiers of order <math>i</math>, beginning with <math>\exists</math>, followed by a formula of order <math>i-1</math>.

Using the standard notation of the [[Tetration#Notation|tetration]], <math>\exp_2^0(x)=x</math> and <math> \exp_2^{i+1}(x)=2^{\exp_2^{i}(x)}</math>. <math> \exp_2^{i+1}(x)=2^{2^{2^{2^{\dots^{2^{x}}}}}}</math> with <math>i</math> times <math>2</math>

=== Normal form ===
Every formula of order <math>i</math>th  is equivalent to a formula in prenex normal form, where we first write quantification over variable of <math>i</math>th order and then a formula of order <math>i-1</math> in normal form.

=== Relation to complexity classes ===
HO is equal to the class [[ELEMENTARY]] of elementary functions.  To be more precise, <math>\mathsf{HO}^i_0 = \mathsf{NTIME}(\exp_2^{i-2}(n^{O(1)}))</math>, meaning a tower of <math>(i-2)</math>  2s, ending with <math>n^c</math>, where <math>c</math> is a constant. A special case of this is that [[NP (complexity)|<math>\exists\mathsf{SO}=\mathsf{HO}^2_0=\mathsf{NTIME}(n^{O(1)})={\color{Blue}\mathsf{NP}}</math>]], which is exactly [[Fagin's theorem]]. Using [[oracle machine]]s in the [[polynomial hierarchy]], [[NTIME|<math>\mathsf{HO}^i_j={\color{Blue}\mathsf{NTIME}}(\exp_2^{i-2}(n^{O(1)})^{\Sigma_j^{\mathsf P}})</math>]]

==Notes==
{{Reflist}}

== References ==
* {{Cite book|first=Neil|last=Immerman|url=http://worldcat.org/oclc/901297152|title=Descriptive complexity|date=1999|publisher=Springer|isbn=0-387-98600-6|oclc=901297152}}

== External links ==
* [http://www.cs.umass.edu/~immerman/descriptive_complexity.html Neil Immerman's descriptive complexity page], including a diagram

[[Category:Descriptive complexity| ]]
[[Category:Computational complexity theory]]
[[Category:Finite model theory]]