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的一个子类）能够执行大量的数值计算，因此包含一些与实场计算相关的复杂性类，以及捕获数值分析中一些基本问题的复杂性。在计数层次结构中仍有几个重要且看似相关的问题尚不清楚；这个项目将调查这些问题是否也存在于计数层次结构中。