Combinatorial Methods in Circuit Complexity

这项研究将开发用于计算特定函数的一般布尔电路的复杂性下界的证明方法。有几个方向看起来很有希望。一种是Sipser的拓扑学方法，其中无限类比提出了应用描述集合论中的概念的方法。第二种是Karchmer，Raz和Wigderson提出的一种通过合成硬函数来获得高深度复杂性的方法。第三种是Razborov提出的一种方法，它是他用来获得单调下界的近似方法的推广。

This research will develop methods for proving lower bounds on the complexity of general Boolean circuits for computing specific functions. Several directions appear promising. One is the topological approach of Sipser, where infinitary analogs suggest ways to apply concepts from descriptive set theory. The second is an approach suggested by Karchmer, Raz and Wigderson for obtaining high depth complexity by composing hard functions. The third is a method suggested by Razborov as a generalization of the approximation method he used to obtain monotone lower bounds.