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

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