MODELING THE COMPLEXITY OF PARALLEL AND VLSI COMPUTATIONS WITH BOOLEAN CIRCUITS

Complexity theory seeks to understand the resource requirements inhere nt in the solution of problems on computers. It also seeks to understa nd the relative computational power of different models. The Turing mo del is difficult to work with, in part because of the impossibility of studying strictly finite structures. Boolean circuits are playing a m ore important role in our understanding of computation. They are usefu l as models in situations as far removed as VLSI design and parallel c omputation. The branching program challenges our intuitions. It has be en shown in an indirect fashion that constant-width branching programs can 'count', but not exactly how. Algebraic methods give a handle and allow us for the first time to study complicated combinatorial struct ures.