Languages which capture complexity classes
Neil Immerman · 1983
We present in this paper a series of languages adequate for expressing exactly those properties checkable in a series of computational complexity classes. For example, we show that a graph property is in polynomial time if and only if it is expressible in the language of first order graph theory together with a least fixed point operator. As another example, a group theoretic property is in the logspace hierarchy if and only if it is expressible in the language of first order group theory together with a transitive closure operator.