Combinatorial Methods in Circuit Complexity

这项研究将开发方法，证明低 一般布尔电路复杂性的界 计算特定功能。 出现了几个方向 很有希望 一种是Sipser的拓扑方法，其中 无限类似物提出了应用概念的方法， 描述集合论 第二种方法是 由Karchmer，Raz和Wigderson获得高深度 复杂度通过组成硬函数。 三是一种方法 建议由拉兹博罗夫作为一个推广的近似 方法，他用来获得单调下界。

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.