constructive mathematics, realizability, computability
propositions as types, proofs as programs, computational trinitarianism
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 17:56:09. See the history of this page for a list of all contributions to it.