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, 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.
$\exist$ HO $^i$ , logic with existential quantifier of order $i$ followed by a formula of order $i-1$ is equal to NTIME( $\exp_2^{i-2}(n^{O(1)})$ )^[1]
HO $^i_j$ =NTIME( $\exp_2^{i-2}(n^{O(1)}))^{\Sigma_j^{\rm P}}$
HO is equal to ELEMENTARY

References

↑ Lauri Hella and José María Turull-Torres (2006), "Computing queries with higher-order logics", Theoretical Computer Science ((what is called "number" in bibtex) ed.) (Essex, UK: Elsevier Science Publishers Ltd.) 355 (2): 197–214, doi:10.1016/j.tcs.2006.01.009, ISSN 0304-3975

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

External links

Neil Immerman's descriptive complexity page, including a diagram

This article is issued from Wikipedia - version of the Monday, September 08, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Descriptive complexity theory

See also

References

Further reading

External links