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的一个子类）能够执行一大类数值计算，因此包含一些与真实的域上的计算相关的复杂性类，以及捕捉数值分析中一些基本问题的复杂性。 有几个重要的和相关的问题，仍然不知道躺在计数层次结构;这个项目将调查这些问题是否也在计数层次结构。