Descriptive complexity theory

The descriptive complexity theory (descriptive complexity theory ) is a subset of the finite model theory, which examines the relationship between the expressive power of logic and complexity theory.

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

Issues and their representation

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

The approach of descriptive complexity theory it is, however, to classify problems in terms of the logical resources, such as the number of quantifiers, number of alternations and, adding further operators, etc..

Each set of a logic induces a class of finite structures that meet him. Thus, the theorem on the structure of the graph of exactly the graph is satisfied that contain at least one edge. Thus, the induced ( trivial ) problem to decide whether a graph has at least one edge.

So that each logic induces a class of structures (or languages), which are expressed by them.

Characterization of NP

Ronald Fagin showed in 1974 that a language is exactly then in NP if there is a sentence in the existential logic of the second stage, which describes. It contains the existential second-order logic over the signature ( existencial second order logic, ESO ) sentences of the form, with a formula of the first stage, which may include not only the predicates the predicates.

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

Is satisfied by exactly the 3- colorable graphs.

It follows from the proof of the theorem of Fagin that the second -order logic ( which also permits universal quantifiers ) the polynomial hierarchy describes.

Further characterizations

After FAGIN set more complexity classes were (often by Neil Immerman ) characterized in this way:

  • The first- order predicate logic with an operator for forming the transitive closure describes NLOGSPACE
  • The first- order predicate logic with a deterministic transitive closure operator for forming the describes LOGSPACE
  • The second- order logic with a transitive closure operator describes PSPACE
  • Different fixed point logics describe P and PSPACE on ordered structures
Fagin's theorem Richard M. Karp
120278
de