Descriptive complexity

Descriptive complexity

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

Specifically, each logical system produces a set of queries expressible in it. The queries 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, [http://www.almaden.ibm.com/cs/people/fagin/ R. Fagin] . [http://www.almaden.ibm.com/cs/people/fagin/genspec.pdf Generalized First-Order Spectra and Polynomial-Time Recognizable Sets] . "Complexity of Computation", ed. R. Karp, SIAM-AMS Proceedings 7, pp. 27-41. 1974.] 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:
* First-order logic defines the class FO, corresponding to AC0, 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.

References

* [http://www.almaden.ibm.com/cs/people/fagin/ R. Fagin] . [http://www.almaden.ibm.com/cs/people/fagin/tcs93.pdf Finite model theory-a personal perspective] . Theoretical Computer Science 116, 1993, pp. 3-31.
* Neil Immerman. [http://www.cs.umass.edu/~immerman/pub/capture.pdf Languages Which Capture Complexity Classes] . "15th ACM STOC Symposium", pp.347-354. 1983.
* [http://www.cs.umass.edu/~immerman/descriptive_complexity.html Neil Immerman's descriptive complexity page] , including a diagram


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • 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… …   Wikipedia

  • Complexity — For other uses, see Complexity (disambiguation). In general usage, complexity tends to be used to characterize something with many parts in intricate arrangement. The study of these complex linkages is the main goal of complex systems theory. In… …   Wikipedia

  • Complexity class — In computational complexity theory, a complexity class is a set of problems of related resource based complexity. A typical complexity class has a definition of the form: the set of problems that can be solved by an abstract machine M using… …   Wikipedia

  • Complexity economics — Economics …   Wikipedia

  • Descriptive set theory — In mathematical logic, descriptive set theory is the study of certain classes of well behaved subsets of the real line and other Polish spaces. As well as being one of the primary areas of research in set theory, it has applications to other… …   Wikipedia

  • Kolmogorov complexity — In algorithmic information theory (a subfield of computer science), the Kolmogorov complexity of an object, such as a piece of text, is a measure of the computational resources needed to specify the object. It is named after Soviet Russian… …   Wikipedia

  • P (complexity) — In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of… …   Wikipedia

  • Query (complexity) — In descriptive complexity, a query is a mapping from structures of one signature to structures of another vocabulary. Neil Immerman, in his book Descriptive Complexity , use[s] the concept of query as the fundamental paradigm of computation (p.… …   Wikipedia

  • NL (complexity) — In computational complexity theory, NL (Nondeterministic Logarithmic space) is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. NL is a… …   Wikipedia

  • Computational complexity theory — is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other. In this context, a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”