descriptive complexity




Complexity theory is an area of research in computer science that aims to determine the amount of resources (time and space usually) that an algorithm needs to decide a query. Descriptive complexity is a branch of complexity theory that uses sentences in finite model theory to describe queries. It turns out that the languages of these sentences directly correspond to known complexity classes?.


  • Neil Immerman, Descriptive Complexity, Graduate texts in computer science (Springer-Verlag New York Inc.) (1999)

  • Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, ed. R. Karp, SIAM-AMS Proceedings, Vol. Vol. 7 (1974):43-73.

Last revised on October 22, 2017 at 13:56:09. See the history of this page for a list of all contributions to it.