Descriptive Complexity

Descriptive complexity characterizes computational complexity classes by the richness of the logic needed to express their problems, replacing machine resources such as time and space with logical definability.

Definition

Descriptive complexity is the branch of finite model theory that classifies decision problems by which logic can define them over finite structures, establishing exact correspondences between complexity classes and logical languages.

Scope

This topic covers Fagin's theorem identifying NP with existential second-order logic, the logical characterizations of P, NL, and PSPACE through fixed-point and transitive-closure logics, the role of order and counting, and the use of finite model theory to study expressive power and to attack questions about complexity classes.

Core questions

• Can computational difficulty be measured by logical expressiveness instead of machine resources?
• Which logic captures NP, and which captures polynomial time?
• Why does the presence of a linear order matter for these characterizations?
• How might logical methods bear on separating complexity classes?

Key theories

Fagin's theorem

A property of finite structures is in NP if and only if it is expressible in existential second-order logic, the founding result that gives a purely logical, machine-free characterization of a major complexity class.

Logical capture of P and PSPACE

On ordered structures, polynomial time corresponds to first-order logic with a least fixed-point operator and polynomial space to first-order logic with a partial fixed-point operator, extending the descriptive program across the complexity hierarchy.

Clinical relevance

Descriptive complexity gives a machine-independent account of tractability that clarifies the expressive power and efficiency of database query languages, since first-order and fixed-point logics correspond to practical query languages, and it offers logical tools that researchers hope may eventually help separate complexity classes.

History

Fagin proved his characterization of NP in 1974, opening the field. Immerman and Vardi independently captured polynomial time by fixed-point logic on ordered structures around 1982, and Immerman's work on nondeterministic space, including the closure of nondeterministic space under complement, further tied logic to complexity.

Debates

Is there a logic capturing polynomial time without order?

Fixed-point logic captures P only when a linear order is available. Whether some logic captures polynomial time on unordered structures is a central open problem, since a negative answer would separate P from NP and a positive one would be a major advance.

Key figures

• Ronald Fagin
• Neil Immerman
• Moshe Vardi
• Bruno Courcelle

Seminal works

• immerman1999
• libkin2004

Frequently asked questions

What does it mean to capture a complexity class with a logic?

It means that exactly the problems in that class are the ones expressible by formulas of the logic over finite structures. Fagin's theorem, for instance, says the NP problems are precisely those definable in existential second-order logic, so membership in the class becomes a question of logical expressibility.

Why does descriptive complexity care about ordering?

Several characterizations, such as fixed-point logic capturing polynomial time, hold only when structures come with a linear order that the logic can use. Without order these logics are weaker, and finding an order-free logic for polynomial time is a deep open problem connected to P versus NP.