Descriptive Complexity Theory

The computational complexity of a problem is the amount of resources, such as time or space, required by a machine that solves the problem. Complexity theory traditionally has focused on the computational complexity of problems. A more recent branch of complexity theory focuses on the descriptive complexity of problems, which is the complexity of describing problems in some logical formalism. One of the exciting developments in complexity theory is the discovery of a very intimate connection between computational and descriptive complexity.

This intimate connection was first discovered by Fagin, who showed that the complexity class NP coincides with the class of properties of finite structures expressible in existential second-order logic. Stockmeyer then observed that this could be extended to give a tight correspondence between the polynomial-time hierarchy and second-order logic. The next discovery was by Immerman and Vardi, who proved that the complexity class P coincides with the class of properties of finite ordered structures expressible in fixpoint logic.

A consequence of the connection between NP and existential second-order logic is that NP=co-NP if and only if existential and universal second-order logic have the same expressive power over finite structures. This equivalence of questions in computational and descriptive complexity is one of the major features of the connection between the two branches of complexity theory. It holds the promise that techniques from one domain could be brought to bear on questions in the other domain.