Descriptive Complexity Theory

The descriptive complexity theory ( descriptive complexity theory ) is a portion of the finite model theory which examines the relationship of the expression strength of logics and complexity theory.

While complexity classes like NP or PSPACE are usually defined by a special machine model (usually Turing machines ), with the help of descriptive complexity theory these classes can also be characterized by "natural" logics such as first or higher level predicate logic or fixed point logics .

Problems and their representation

In classical complexity theory, problems are examined in terms of which computer resources (space, time, number of circuits ...) are required to solve them.

The approach of descriptive complexity theory, on the other hand, is to classify problems with regard to logical resources , such as the number of quantifiers, number of alternations of and , addition of further operators, etc. ${\displaystyle \exists }$ ${\displaystyle \forall }$

Every set of logic induces a set of finite structures that satisfy it. So the theorem about the structure of the graphs is fulfilled by precisely those graphs that contain at least one edge. So the (trivial) problem induces us to decide whether a graph has at least one edge. ${\displaystyle \varphi :=\exists x\exists yE(x,y)}$ ${\displaystyle {E}}$ ${\displaystyle \varphi }$

Every logic thus induces a class of structures (or: languages) that can be expressed through it. Probably the first result in this direction is Büchi's theorem , according to which the regular languages ​​are exactly the languages that can be defined in the second-order monadic predicate logic .

Characterization of NP

Ronald Fagin showed in 1974 that a language is in NP if and only if there is a sentence in the existential logic of the second level that describes it. The existential logic includes second stage over the signature ( existencial second order logic , ESO ) sentences of the form , wherein , in addition to the predicates a formula of the first stage is the predicates may contain. ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle \{Q_{1},\ldots ,Q_{k}\}}$ ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle \exists P_{1}\ldots P_{k}\,\varphi }$ ${\displaystyle \varphi }$ ${\displaystyle Q_{1},\ldots ,Q_{k}}$ ${\displaystyle P_{1},\ldots ,P_{k}}$

For example, the problem of 3-colorability lies in NP, since the theorem

${\displaystyle {\begin{aligned}\exists C_{1}\exists C_{2}\exists C_{3}&&\underbrace {\forall v((C_{1}(v)\wedge \neg C_{2}(v)\wedge \neg C_{3}(v))\vee (\neg C_{1}(v)\wedge C_{2}(v)\wedge \neg C_{3}(v))\vee (\neg C_{1}(v)\wedge \neg C_{2}(v)\wedge C_{3}(v))} _{\text{jeder Knoten ist mit genau einer Farbe gefaerbt}}\\&&\wedge \underbrace {\forall u\forall vE(u,v)\rightarrow \neg ((C_{1}(u)\wedge C_{1}(v))\vee (C_{2}(u)\wedge C_{2}(v))\vee (C_{3}(u)\wedge C_{3}(v)))} _{\text{keine zwei adjazenten Knoten haben die gleiche Farbe}}\end{aligned}}}$

is fulfilled by exactly the 3-colorable graph.

From the proof of Fagin's theorem it follows that the logic of the second level (which also allows universal quantifiers) describes the polynomial hierarchy .

Further characterizations

Following Fagin's theorem, further complexity classes were characterized in this way (often by Neil Immerman ):

• NLOGSPACE describes the first-level predicate logic with an operator to form the transitive envelope
• LOGSPACE describes the first level predicate logic with a deterministic operator to form the transitive envelope
• The logic of the second level with a transitive shell operator describes PSPACE
• various fixed point logics describe P or PSPACE on ordered structures

literature

• Ronald Fagin. Finite model theory-a personal perspective (PDF; 2.3 MB). Theoretical Computer Science 116, 1993, pp. 3-31.
• Neil Immerman. Languages ​​Which Capture Complexity Classes (PDF; 459 kB). 15th ACM STOC Symposium , pp. 347-354. 1983.
• Heinz-Dieter Ebbinghaus, Jörg Flum. Finite Model Theory, pp. 119-164. 1999.

swell

1. ↑ JR Büchi: Weak second-order arithmetic and finite automota , Journal for mathematical logic and foundations of mathematics (1960), Volume 6, pages 66-92
2. ^ Leonid Libkin: Elements of Finite Model Theory , Springer-Verlag (2004), ISBN 3-540-21202-7 , sentence 7.21
3. ↑ Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets, in: Complexity of Computation by Richard M. Karp (Ed.)