Complexity of Small-Depth Circuits

点击翻译按钮获取中文摘要

The proposed research is part of a continuing study of the computational complexity of boolean circuits and related models of computation, such as threshold circuits and branching programs. All the problems to be investigated concern the manner in which the size, depth and type of gates in a circuit affect its computational power. The focus is on circuit whose depth is small (either independent of input length or logarithmic in input length) and whose size is either bounded by a polynomial in the input length or is slightly larger. The principal goal is to prove that certain problems cannot be solved under such size and depth restrictions, and thereby determine the structure of complexity classes defined by small-depth circuit families. These questions will be investigated by two distinct methods: The first is the representation of the behavior of the circuit or the program by polynomials or similar algebraic objects, and the use of Fourier analysis to discover properties of these representations. The second is the representation of a circuit's behavior as a program over a finite monoid, which permits the application of methods from the global structure theory of finite semigroups.