Hierarchies, Circuit Lower Bounds and Pseudorandomness

计算复杂性理论研究高效计算的可能性和局限性。这个领域的中心问题是P与NP问题，它询问是否每个在非确定多项式时间(NP)可解的计算问题在确定多项式时间(P)也是可解的。在P中的可解性通常表明在现实世界中是可行的。NP与P的问题是至关重要的，因为一些重要的问题，如布尔可满足性，整数线性规划和团，已知在NP中，但不知道是有效可解的。克莱数学研究所已将NP与P问题列为其七个“千年问题”之一，并提供100万美元来解决这个问题--这表明它不仅在计算机科学中，而且在数学中也是核心问题。这个问题也与其他几个领域有关，如经济学、生物学和物理学，因为在这些领域也有一些重要的问题，这些问题已知存在于NP中，而不是已知存在于P中。人们普遍认为NP不等于P，然而似乎很难给出这一点的形式证明。这在很大程度上是因为计算复杂性的上界和下界之间的根本区别。只要给出一个在多项式时间内运行并解决问题的算法，就可以证明一个问题在(确定性)多项式时间内。然而，要证明一个问题不在多项式时间内，需要证明每个多项式时间算法都不能解决这个问题。这要困难得多，因为多项式时间是一种相对丰富的计算模型--似乎很难分离出在多项式时间可解问题的共同之处的结构特征。NP与P的问题似乎不是现有技术所能达到的，然而，还有其他更容易实现的下界问题，如层次结构问题和固定多项式回路下界问题。这些问题有它们自己的自然动机--层次结构问题问的是，如果给定更多的资源，比如概率时间，是否可以解决更多的问题，而电路下限问题问的是，一个问题是否可以在硬件上有效地解决。这些问题彼此密切相关，也与去随机化概率算法的问题密切相关。实践中使用的许多算法都假定可以访问独立且无偏的随机比特源。然而，还不清楚真实世界中是否存在真正的随机性。因此，将算法的随机性要求降到最低是很有意义的。伪随机性理论恰恰解决了这个问题--算法的随机性要求可以最小化到什么程度？这与密码学和安全性尤其相关，因为任何密码协议都必须使用随机性才是安全的，而使用不完全随机可能会使协议变得不安全。我们建议研究层次结构、电路下界和去随机化问题，以及它们之间的联系。我们的目标是证明新的下界，并在这样做的过程中制定新的较低的技术，这些技术可能会有其他应用，甚至最终可能会应用到NP与P的问题上。我们还为这些基本问题的研究制定了两个新的方向，这两个方向与有限模型理论和证明复杂性有关。希望来自这些其他领域的观点和见解可以补充既定的想法，以便在这些重要和困难的问题上取得进展。

Computational complexity theory studies the possibilities and limits of efficient computation. The central question in this area is the P vs NP question, which asks if every computational problem solvable in non-deterministic polynomial time (NP) is also solvable in deterministic polynomial time (P). Solvability in P typically indicates feasibility in the real world.The NP vs P question is critical because several important problems, such as Boolean satisfiability, Integer Linear programming and Clique, are known to be in NP but not known to be efficiently solvable. The Clay Mathematics Institute has listed the NP vs P question among its seven ``Millennium Problems'' and offered 1,000,000 dollars for its solution - an indication of its centrality not just in computer science but also in mathematics. The question is also relevant to several other fields such as economics, biology and physics, because there are important problems in these fields as well which are known to be in NP but not known to be in P.It is widely believed that NP does not equal P, however it seems dauntingly hard to give a formal proof of this. A large part of the reason for this is the fundamental distinction between upper bounds and lower bounds on computational complexity. Proving that a problem is in (deterministic) polynomial time can be done just by giving an algorithm that runs in polynomial time and solves the problem. However, proving that a problem is not in polynomial time requires showing that every polynomial time algorithm fails to solve the problem. This is considerably harder because polynomial time is a relatively rich model of computation - it seems hard to isolate structural features which problems solvable in polynomial time have in common. The NP vs P question seems out of reach of current techniques, however there are other lower bounds questions which are more accessible such as the hierarchies question and the fixed polynomial circuit lower bounds question. These have natural motivations of their own - the hierarchies question asks whether more problems can be solved given more of a given resource, say probabilistic time, while the circuit lower bounds question asks if a problem can be solved efficiently in hardware. These questions are closely connected to each other, as well as to the question of derandomizing probabilistic algorithms. Many algorithms used in practice assume access to an independent and unbiased source of random bits. However, it's unclear whether true randomness exists in the real world. Thus it is of interest to minimize the randomness requirements of algorithms. The theory of pseudo-randomness addressed precisely this question - to what extent can randomness requirements of algorithms be minimized? This is particularly relevant to cryptography and security, since any cryptographic protocol must use randomness to be secure, and using imperfect randomness may make a protocol insecure.We propose to study hierarchies, circuit lower bounds and derandomization questions in this project, as well as the connections between them. Our goal is to prove new lower bounds, and in the process of doing so to formulate new lower techniques which could have other applications, perhaps ultimately even to the NP vs P question. We have also formulated two new directions for research on these fundamental problems, which connect to finite model theory and proof complexity. The hope is that perspectives and insights from these other areas might complement established ideas to achieve progress on these important and difficult problems.