Combinatorial Methods in Circuit Complexity

电路复杂性中的组合方法

• 批准号: 9212184
• 负责人: Michael Sipser
• 金额: --
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-09-15 至 1997-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9212184&HistoricalAwards=false
• 关键词: Combinatorial; Methods; Circuit; Complexity

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.

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