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.