Descriptive complexity theory

For other uses, see Kolmogorov complexity.

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

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.

The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974. 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. Many other classes were later characterized in such a manner, most of them by Neil Immerman:

• 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.
• Universal second-order logic (excluding existential second-order quantification) yields co-NP.
• Second-order logic corresponds to PH, as mentioned above.
• 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.
• $\exists {\color {Blue}{\mathsf {HO}}}^{i}$, logic with existential quantifier of order i followed by a formula of order $i-1$ is equal to ${\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)}))$
• ${\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)}))^{\Sigma _{j}^{\mathsf {P}}}$
• HO is equal to ELEMENTARY

See also

• SO (complexity)
• FO (complexity)
• Spectrum of a sentence

References

• Ronald Fagin, Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings 7, pp. 27–41. 1974.
• Ronald 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.
• Immerman, Neil (1999). Descriptive Complexity. New York: Springer-Verlag. pp. 113–119. ISBN 0-387-98600-6..

Further reading

• Shawn Hedman, A first course in logic: an introduction to model theory, proof theory, computability, and complexity, Oxford University Press, 2004, ISBN 0-19-852981-3, section 10.3 is a suitable introduction for undergraduates
• Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Maarten, Marx; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. ISBN 978-3-540-00428-8. Zbl 1133.03001.

External links

• Neil Immerman's descriptive complexity page, including a diagram