Computational Complexity Theory and Circuit Complexity

这个项目的重点是计算复杂性理论中的问题，目的是澄清各种重要的算法类别(称为“复杂性类别”)的能力和局限性。复杂性类为理解真实世界计算问题的计算复杂性提供了目前可用的最好工具。这一领域的最新进展引起了(谨慎的)乐观情绪，即可以找到一些途径，通过利用“强向下自约简”的性质，避免证明计算各种函数所需的电路大小的下界的一些已知障碍。对于具有这种性质的问题，适度的下界可以被“放大”以获得超多项式的下界。该项目旨在调查这一新方法的威力和适用性。同时，我们将调查某些研究得很好的证明系统是否无法证明甚至是引导这一“放大”程序所需的适度下限。该项目还将研究证明条件电路下界的其他方法。该项目还将致力于建立在最近的发现的基础上，即‘计数层次’(PSPACE的一个子类)能够执行一大类数值计算，从而包含一些与实数域上的计算相关的复杂性类，以及捕捉数值分析中一些基本问题的复杂性。有几个重要的和看似相关的问题仍然不知道存在于计数层次结构中；本项目将调查这些问题是否也存在于计数层次结构中。

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.