In the world of circuit complexity the easiest
problems to solve are those in the class AC0,
solvable by AND/OR circuits of constant depth,
polynomial size, and unbounded fan-in. In the
world of descriptive complexity the easiest problems
to describe are those that correspond to formulas
of first-order logic. In fact these two classes
of problems are equal. We will prove both the non-uniform
and uniform versions of this result (the latter
from Barrington-Immerman-Straubing 1990), and
consider ways in which it extends to more powerful
complexity classes.
Last modified 1 March 2003