Descriptive complexity
Descriptive complexity is a branch of finite model theory, a subfield of computational complexity theory and mathematical logic, in which we seek to characterize complexity classes by the type of logic needed to express the languages in them. For example, PH is precisely the class of languages expressible by statements of second-order logic. This connection between complexity and logic 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 machines used to define them. The first main result of descriptive complexity, shown by Ronald Fagin in 1974, is that NP is precisely the set of languages expressible by sentences of existential second-order logic — that is, second order logic excluding universal quantification over relations, functions, and subsets. Many other classes were later characterized in such a manner, most of them by Neil Immerman: First-order logic corresponds to AC0, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time. First-order logic with a commutative, transitive closure operator added yields SL, which equals L, problems solvable in logarithmic space. First-order logic with a transitive closure operator yields NL, the problems solvable in nondeterministic logarithmic space. First-order logic with a least fixed point operator gives P, the problems solvable in deterministic polynomial time. Existential second-order logic yields NP, as mentioned above. Universal second-order logic (excluding existential second-order quantification) yields co-NP. Second-order logic corresponds to PH. Second-order logic with a transitive closure (commutative or not) yields PSPACE, the problems solvable in polynomial space. Second-order logic with a least fixed point operator gives EXPTIME, the problems solvable in exponential time.
References
|
|
