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.