Low-Level Complexity
Perhaps the hardest thing to prove about a computational model is
that it cannot solve a given problem within particular resource constraints.
Such ``lower bounds'' are currently solvable only when the model is
very specialized or the constraints are very severe. The research project
in low-level complexity attempts to attack such problems by determining
the relationships between complexity classes defined in various models
by such very severe constraints. In particular, the class
NC1 (problems
solvable by Boolean circuits of logarithmic depth) has a rich internal
structure of subclasses, normally defined by different kinds of circuits.
Our researchers have found that these same subclasses can
also be defined by placing natural constraints on several apparently unrelated
models of computation, such as branching programs, finite automata,
and first-order logic. These relationships have led to new lower bound
results and pointed the way to many new problems.