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.

复杂性理论的研究目标是通过提供解决真实的世界计算问题所需资源的下限来对这些问题的复杂性进行分类。 到目前为止-尽管令人印象深刻的下限限制类型的电路-几乎唯一有用的进展，朝着这一目标已经通过工具的约简，它允许一个人来表明，问题是完全的复杂性类。许多最重要的复杂性类可以特征化的布尔电路的限制大小或深度等。最近，显然，算术电路在这方面也非常有用。 布尔和算术电路复杂性之间的关系仍然知之甚少，尽管最近在这方面取得了重大进展。 本项目将进一步阐明这些关系，特别是对算术运算的复杂性进行新的探索，研究小空间限制复杂性类和小深度电路定义复杂性类的能力。 此外，Kolmogorov复杂性的工具将被应用，以获得更好的理解图的可达性问题的复杂性。 更一般地说，该项目将试图澄清复杂性类之间的关系，以及各种概念（非确定性，无二义性，对称性，布尔和算术电路等）。它定义了计算模型，描述了重要的复杂性类别。