Descriptive complexity theory

Summary

Descriptive complexity theory characterizes complexity classes by the logics needed to define their problems. It treats an input as a finite structure, such as a graph, and asks how rich a logic must be to express a property. The founding result is Fagin's theorem: NP is the class of properties definable in existential second-order logic. It is a part of finite model theory. Later results characterize P, NL and PSPACE on ordered structures by extensions of first-order logic with fixed points or transitive closure.