The project examines the structure of classes of problems solvable by constant-depth families of circuits biult from unbounded fan-in gates of various descriptions. All of the classes under consideration are contained in the complexity class NC1, which is a model for the family of problems solvable by very fast parallel algorithms. The principal goal of the research is to answer a number of open questions concerning the inclusions among these classes; in particular, to settle the question of wheather either iterated addition mod m or the majority problem is complete for NC1 with respect to constant-depth reductions. This work will employ the recently discovered characterization of NC1 and its subclasses in terms of formal logic and finite automata. These characterizations make it possible to apply model-theoretic and algebraic methods to the study of circuit complexity. It is hoped that, in addition to settling these immediate questions, a new methodology for proving lower bounds in computational complexity will result, and that this will be of benefit in studying classes of higher complexity.
