Descriptive Complexity


Computational complexity was originally defined in terms of the natural entities of time and space, and the term complexity was used to denote the time or space used in the computation. Rather than checking whether an input satisfies a property S, a more natural question might be, what is the complexity of expressing the property S? These two issues -- checking and expressing -- are closely related. It is startling how closely tied they are when the latter refers to expressing the property in first-order logic of finite and ordered structures. In 1974 Fagin gave a characterization of nondeterministic polynomial time as the set of properties expressible in second-order existential logic. Extending this theorem, our research has related first-order expressibility to computational complexity. Some of the results arising from this approach include characterizing polynomial time as the set of properties expressible in first-order logic plus a least fixed-point operator, and showing that parallel time on a Parallel Random Access Machine is linearly related to first-order inductive depth. This research has settled a major, long standing question in complexity theory by proving the following result: For all s(n) greater than or equal to log n, nondeterministic space s(n) is closed under complementation.

See Neil Immerman's Recent Publications, for available on-line publications on descriptive complexity, and "Introductory Survey of Descriptive Complexity", for slides of a recent survey talk on Descriptive Complexity.


Natural complexity classes tend to have natural descriptive characterizations. For example, here is a diagram of the world of computability and complexity:


In the above diagram, CRAM[t(n)] is parallel time O(t(n)) on a Concurrent-Read, Concurrent-Write Parallel Random Access Machine, using polynomially much hardware. This is equal to FO[t(n)], the set of problems expressible by a fixed block of first-order restricted quantifiers, recopied t(n) times for structures of size n. CH[t(n),h(n)] is parallel time O(t(n)) on a CRAM using O(h(n)) hardware gates.

The following are descriptive characterizations of some of the above classes. We think of all complexity theoretic problems as sets of finite structures of some vocabulary. Such a problem can be thought of as a boolean-valued query on relational databases. The following characterizations assume that there is a given total ordering on each input structure.


Descriptive Complexity is part of Finite Model Theory, a branch of Logic and Computer Science.

Thanks to NSF grants CCR-8105754, Mathematical Sciences Postdoctoral Research Fellowship 8311679, CCR-8603346, CCR-8806308, CCR-8996280, CCR-9008416, CCR-9207797, CR-9505446, CCR-9877078, CCF-0207373, CCF-0514621, CCF-0830174, CCF-1115448, CCF-1617498 which helped to support some of the research described on this page.