Editing Descriptive complexity theory (section)

{{Short description|Branch of mathematical logic}}

'''Descriptive complexity''' is a branch of [[computational complexity theory]] and of [[finite model theory]] that characterizes [[complexity class]]es by the type of [[logic]] needed to express the [[formal language|language]]s in them. For example, [[PH (complexity)|PH]], the union of all complexity classes in the polynomial hierarchy, is precisely the class of languages expressible by statements of [[second-order logic]]. This connection between complexity and the logic of finite structures allows results to be transferred easily from one area to the other, facilitating new proof methods and providing additional evidence that the main complexity classes are somehow "natural" and not tied to the specific [[abstract machine]]s used to define them.

Specifically, each [[logical system]] produces a set of [[query (complexity)|queries]] expressible in it. The queries – when restricted to finite structures – correspond to the [[computational problem]]s of traditional complexity theory.

The first main result of descriptive complexity was [[Fagin's theorem]], shown by [[Ronald Fagin]] in 1974. It established that [[NP (complexity)|NP]] is precisely the set of languages expressible by sentences of existential [[second-order logic]]; that is, second-order logic excluding [[universal quantification]] over [[relation (mathematics)|relation]]s, [[function (mathematics)|function]]s, and [[subset]]s. Many other classes were later characterized in such a manner.