Computational Complexity Theory and Circuit Complexity

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

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

This project focuses on problems in computational complexity theory, with the goal of clarifying the power and limitations of various important classes of algorithms (known as ``complexity classes''). Complexity classes provide the best tools currently available for understanding the computational complexity of real-world computational problems.Recent progress in the field has given rise to (cautious) optimism that routes can be found that avoid some of the known barriers to proving lower bounds on the circuit size required to compute various functions, by capitalizing on the property of ``strong downward self-reducibility''. For problems that possess this property, modest lower bounds can be ``amplified'' to obtain superpolynomial lower bounds. This project aims to investigate the power and applicability of this new approach. In parallel, we will investigate whether certain well-studied proof systems are incapable of proving even the modest lower bounds that would be required in order to bootstrap this ``amplification'' procedure. The project also will investigate other approaches to proving conditional circuit lower bounds.The project will also aim to build on the recent discovery that that the ``counting hierarchy'' (a subclass of PSPACE) is able to perform a large class of numerical computations, and thus contains some complexity classes related to computation over the real field, as well as capturing the complexity of some fundamental problems in numerical analysis. There are several important and seemingly-related problems that are still not known to lie inside the counting hierarchy; this project will investigate whether these problems also are in the counting hierarchy.

该项目重点关注计算复杂性理论中的问题，目的是阐明各种重要算法类别（称为“复杂性类别”）的能力和局限性。 复杂性类别提供了当前可用于理解现实世界计算问题的计算复杂性的最佳工具。该领域的最新进展引起了（谨慎）乐观的看法，即可以找到路线，避免一些已知的证明下限的障碍通过利用“强向下自还原性”的特性来计算各种函数所需的电路大小。 对于具有此属性的问题，可以“放大”适度的下界以获得超多项式下界。 该项目旨在研究这种新方法的威力和适用性。 与此同时，我们将调查某些经过充分研究的证明系统是否无法证明引导这种“放大”过程所需的适度下限。 该项目还将研究证明条件电路下界的其他方法。该项目还将致力于以最近的发现为基础，即“计数层次结构”（PSPACE 的子类）能够执行大量数值计算，因此包含一些与实域计算相关的复杂性类，以及捕获数值分析中一些基本问题的复杂性。 有几个重要且看似相关的问题仍然不知道存在于计数层次结构中；该项目将调查这些问题是否也在计数层次中。