Computational Complexity Theory and Circuit Complexity

计算复杂性理论和电路复杂性

• 批准号: 0104823
• 负责人: Eric Allender
• 金额: $ 26.8万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0104823&HistoricalAwards=false
• 关键词: Computational; Complexity; Theory; Circuit

The goal of research in complexity theory is to classify the complexity of real world computational problems by providing lower bounds on the resources required to solve them. To date - in spite of impressive lower bounds for restricted types of circuits- almost the only useful progress toward this goal has come via the tool of reducibility, which allows one to show that problem is complete for complexity class.Many of the most important complexity classes can be characterized in terms of Boolean circuits of restricted size or depth, etc. Recently, it has become apparent that arithmetic circuits are also very useful in this regard. The relationships between Boolean and arithmetic circuit complexity are still only poorly understood, although there has been significant progress on this front recently. This project will work to clarify these relationships further.Specially, this project will exploit new insights about the complexity of arithmetic operation, in order to investigate the power of small space-bounded complexity classes and complexity classes defined in terms of small-depth circuits. Also the tools of Kolmogorov complexity will be applied, in order to obtain a better understanding of the complexity of graph reachability problems. More generally, the project will attempt to clarify the relationship among complexity classes, and the various notions (nondeterminism, unambiguity, symmetry, Boolean and arithmetic circuits, etc.) that define models of computation characterizing important complexity classes.

复杂性理论研究的目标是通过提供解决问题所需资源的下限来对现实世界计算问题的复杂性进行分类。 迄今为止，尽管受限类型的电路具有令人印象深刻的下限，但实现这一目标的唯一有用进展几乎是通过可简化性工具来实现的，它允许人们证明复杂性类别的问题是完整的。许多最重要的复杂性类可以用受限大小或深度的布尔电路等来表征。最近，很明显算术电路在这方面也非常有用。 尽管最近在这方面取得了重大进展，但布尔和算术电路复杂性之间的关系仍然知之甚少。 该项目将致力于进一步阐明这些关系。特别是，该项目将利用关于算术运算复杂性的新见解，以研究小空间有限复杂性类和根据小深度电路定义的复杂性类的威力。 还将应用柯尔莫哥洛夫复杂度工具，以便更好地理解图可达性问题的复杂性。 更一般地说，该项目将尝试澄清复杂性类别之间的关系，以及定义表征重要复杂性类别的计算模型的各种概念（不确定性、明确性、对称性、布尔和算术电路等）。