Descriptive complexity is a branch of finite model theory, a subfield of computational complexity theory and mathematical logic, which seeks to characterize complexity classes by the type of logic needed to express the languages in them. For example, PH is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and logic 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. Finite model theory is a subfield of model theory that focuses on properties of logical languages, such as first-order logic, over finite structures, such as finite groups, graphs, databases, and most abstract machines. ... As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ... Mathematical logic is a subfield of mathematics that is concerned with formal systems in relation to the way that they encode intuitive concepts of mathematical objects such as sets and numbers, proofs, and computation. ... In computational complexity theory, a complexity class is a set of problems of related complexity. ... In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE. PH has... In mathematical logic, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. ... An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in Automata theory. ...

Specifically, each logical system produces a set of queries expressible in it. The queries correspond to the computational problems of traditional complexity theory. In descriptive complexity, a query is a mapping from structures of one vocabulary to structures of another vocabulary. ... In theoretical computer science, a computational problem is a mathematical object representing a question that computers might want to solve. ...

The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974,^[1] which 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. Many other classes were later characterized in such a manner, most of them by Neil Immerman: There are very few or no other articles that link to this one. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In mathematical logic, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. ... Neil Immerman is one of the key developers of an active research program called Descriptive Complexity, an approach he is currently applying to research in model checking, database theory, and computational complexity theory. ...

• First-order logic defines the class FO, corresponding to AC⁰, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time.
• First-order logic with a commutative, transitive closure operator added yields SL, which equals L, problems solvable in logarithmic space.
• First-order logic with a transitive closure operator yields NL, the problems solvable in nondeterministic logarithmic space.
• In the presence of linear order, first-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time.
• Existential second-order logic yields NP, as mentioned above.
• Universal second-order logic (excluding existential second-order quantification) yields co-NP.
• Second-order logic corresponds to PH.
• Second-order logic with a transitive closure (commutative or not) yields PSPACE, the problems solvable in polynomial space.
• Second-order logic with a least fixed point operator gives EXPTIME, the problems solvable in exponential time.

First-order logic (FOL) is a universal language in symbolic science, and is in use everyday by mathematicians, philosophers, linguists, computer scientists and practitioners of artificial intelligence. ... This article does not cite any references or sources. ... In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ... In computational complexity theory, SL (Symmetric Logspace) is the complexity class of problems log-space reducible to USTCON, which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same... In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. ... In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ... In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ... In mathematics, the least fixed point in order theory of a function is the fixed point which is less than or equal to all other fixed points, according to some partial order. ... In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE. PH has... In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... In mathematics, the least fixed point in order theory of a function is the fixed point which is less than or equal to all other fixed points, according to some partial order. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ...

References

1. ^ R. Fagin. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, pp. 27-41. 1974.

• R. Fagin. Finite model theory-a personal perspective. Theoretical Computer Science 116, 1993, pp. 3-31.
• Neil Immerman. Languages Which Capture Complexity Classes. 15th ACM STOC Symposium, pp.347-354. 1983.
• Neil Immerman's descriptive complexity page, including a diagram