# Descriptive complexity theory

**descriptive complexitydescriptional complexitylogical characterization**

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.wikipedia

43 Related Articles

### Complexity class

**complexity classescomputational complexityclasses**

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.

Many complexity classes can be characterized in terms of the mathematical logic needed to express them; see descriptive complexity.

### Finite model theory

**finite modelsfinite model**

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.

As MT is closely related to mathematical algebra, FMT became an "unusually effective" instrument in computer science. In other words: "In the history of mathematical logic most interest has concentrated on infinite structures....Yet, the objects computers have and hold are always finite. To study computation we need a theory of finite structures." Thus the main application areas of FMT are: descriptive complexity theory, database theory and formal language theory.

### Query (complexity)

**queryqueries**

Specifically, each logical system produces a set of queries expressible in it. The queries – when restricted to finite structures – correspond to the computational problems of traditional complexity theory.

In descriptive complexity, a query is a mapping from structures of one signature to structures of another vocabulary.

### Fagin's theorem

**Fagin 1974**

The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974.

Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP.

### FO (complexity)

**FOfirst-order**

First-order logic defines the class FO, corresponding to AC 0, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time.

In descriptive complexity, a branch of computational complexity, FO is a complexity class of structures that can be recognized by formulas of first-order logic, and also equals the complexity class AC 0 . Descriptive complexity uses the formalism of logic, but does not use several key notions associated with logic such as proof theory or axiomatization.

### PH (complexity)

**PHpolynomial hierarchy PHpolynomial hierarchy**

For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. Second-order logic corresponds to PH, as mentioned above.

PH has a simple logical characterization: it is the set of languages expressible by second-order logic.

### Neil Immerman

**Immerman**

Many other classes were later characterized in such a manner, most of them by Neil Immerman:

He is one of the key developers of descriptive complexity, an approach he is currently applying to research in model checking, database theory, and computational complexity theory.

### Computational complexity theory

**computational complexitycomplexity theorycomplexity**

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.

Descriptive complexity theory

### Second-order logic

**second-ordersecond order logicexistential second-order logic**

For example, PH, the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of second-order logic. It established that NP is precisely the set of languages expressible by sentences of existential second-order logic; that is, second order logic excluding universal quantification over relations, functions, and subsets.

The field of descriptive complexity studies which computational complexity classes can be characterized by the power of the logic needed to express languages (sets of finite strings) in them.

### AC0

**AC 0 ACAC''' 0**

First-order logic defines the class FO, corresponding to AC 0, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time.

From a descriptive complexity viewpoint, DLOGTIME-uniform AC 0 is equal to the descriptive class FO+BIT of all languages describable in first-order logic with the addition of the BIT predicate, or alternatively by FO(+, ×), or by Turing machine in the logarithmic hierarchy.

### NP (complexity)

**NPnondeterministic polynomial timeclass NP**

It established that NP is precisely the set of languages expressible by sentences of existential second-order logic; that is, second order logic excluding universal quantification over relations, functions, and subsets.

In terms of descriptive complexity theory, NP corresponds precisely to the set of languages definable by existential second-order logic (Fagin's theorem).

### SO (complexity)

**Second-ordersecond-order logicsecond-order logic over finite structures**

Second-order logic corresponds to PH, as mentioned above.

In descriptive complexity we can see that the languages recognised by SO formulae are exactly equal to the languages decided by Turing machines in the polynomial hierarchy.

### HO (complexity)

**High orderhigh order queries**

[[HO (complexity)|]], logic with existential quantifier of order followed by a formula of order i-1 is equal to [[NTIME|]] HO is equal to ELEMENTARY

In descriptive complexity we can see that it is equal to the ELEMENTARY functions.

### Least fixed point

**greatest fixed pointleast fixpointfixed point logic**

In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time.

independently showed the descriptive complexity result that the polynomial-time computable properties of linearly ordered structures are definable in FO(LFP), i.e. in first-order logic with a least fixed point operator.

### Spectrum of a sentence

Spectrum of a sentence

Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP.

### P (complexity)

**Ppolynomial timepolynomial-time**

In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time.

In descriptive complexity, P can be described as the problems expressible in FO(LFP), the first-order logic with a least fixed point operator added to it, on ordered structures.

### PSPACE

**polynomial spaceAPhard**

Second-order logic with a transitive closure (commutative or not) yields PSPACE, the problems solvable in polynomial space.

A logical characterization of PSPACE from descriptive complexity theory is that it is the set of problems expressible in second-order logic with the addition of a transitive closure operator.

### ELEMENTARY

**elementary recursiveelementary recursive functionbounded sums and products**

HO is equal to ELEMENTARY

In descriptive complexity, ELEMENTARY is equal to the class of high order queries.

### Logic

**logicianlogicallogics**

### Abstract machine

**abstract computerabstract computer modelcomputational models**

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 machines used to define them.

### Formal system

**logical systemdeductive systemsystem of logic**

Specifically, each logical system produces a set of queries expressible in it. The queries – when restricted to finite structures – correspond to the computational problems of traditional complexity theory.

### Computational problem

**computational problemsproblemdecision problem**

Specifically, each logical system produces a set of queries expressible in it. The queries – when restricted to finite structures – correspond to the computational problems of traditional complexity theory.

### Ronald Fagin

The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974.

### First-order logic

**predicate logicfirst-orderpredicate calculus**

First-order logic defines the class FO, corresponding to AC 0, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time.

### Parallel random-access machine

**PRAMparallel random access machineconcurrent random access machine**