Descriptive complexity is a branch of computational complexity where complexity classes are described using forms of logic, giving machine-independent characterizations of the complexity classes. In this talk, we look at an important result in descriptive complexity:
[BIS88, Theorem 8.1] A class of structures is in DLOGTIME-uniform AC0 if and only if the class is definable in first-order logic with numerical predicates.
Here, DLOGTIME is the class of languages accepted by a deterministic random-access Turing machine in logarithmic time.
A language is said to be in DLOGTIME-uniform AC0 if it can be recognized by a family of constant-depth, polynomial-size circuits with AND and OR gates, where the circuits can be constructed by a DLOGTIME machine. The proof involves showing that if a language is in DLOGTIME, then it is definable in first-order logic with numerical predicates.
Reference:
[BIS88] David A. Mix-Barrington, Neil Immerman, and Howard Straubing. 1990. On uniformity within NC1. J. Comput. Syst. Sci. 41, 3 (Dec. 1990), 274–306. https://doi.org/10.1016/0022-0000(90)90022-D
