AF: Small: Lower Bounds in Complexity Theory Via Algorithms

计算机通过自动化和帮助人们更有效地工作，几乎改变了生活的方方面面。但是，尽管研究人员对计算机能做什么知道得很多，但对计算机不能做什么却知之甚少。这种现象就是证明“复杂度下界”的问题。下界是我们这个时代最大的科学谜团之一：有许多关于下界的数学猜想和信念——事实上，互联网和密码学的安全性依赖于这些猜想的真实性——但具体的结果很少。这个项目的主要目标是利用人类对计算机算法的丰富知识来证明新的下限：换句话说，目标是利用计算机的能力来证明它们的局限性。第二个目标是研究这些联系的科学后果。一个理论框架的潜在影响——社会的、科学的和其他方面的——很难被高估，它将导致对计算机能做什么和不能做什么的细粒度理解。该项目的另一个目标是使复杂性研究更接近现实世界的计算，并向从业者介绍将影响他们工作的复杂性方面。最后一个目标是教育推广，通过在线论坛致力于学习计算机科学，并与媒体合作，向公众传播理论计算机科学。举一个下界的例子，计算机科学中的一个中心问题是著名的P对NP开放问题，它是关于允许短解的组合问题的难度。这样的问题总是可以通过暴力解决，尝试所有可能的解决方案。蛮力总能被更聪明的搜索方法所取代吗？这个问题很重要；目前还没有令人满意的答案，具体的答案似乎还很遥远。传统的观点认为，一般来说，蛮力是无法完全避免的，但在数学上，大多数自然搜索问题都可以非常迅速地解决，而不需要任何蛮力。否定结果表明，大多数已知的证明方法不能证明强下界，这阻碍了数学理论的发展。这个项目的主要目标是帮助发现和发展新的思维方式，这将揭开下限的神秘面纱，并阐明计算的极限和可能性。这个项目的主要假设是，从算法的角度来看下界是关键：例如，由同一研究小组领导的一个早期项目表明，电路可满足性问题（略优于蛮力搜索）的算法暗示了电路复杂性的下界。其他算法问题，如在不使用随机性的情况下估计电路的可接受概率，以及找到证明一段代码不能正确计算函数的“坏”输入，也被证明对证明下界很有用。潜在的科学应用是巨大的，从逻辑电路设计到网络算法，到改进的硬件和软件测试，到更好的最近邻搜索（在计算机视觉，DNA测序和机器学习中有自己的应用），以及密码学和安全性。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Computers have transformed nearly every aspect of life, by automating and assisting in helping people work more efficiently. But while researchers know much about what computers can do, there is still comparatively little known about what computers cannot do. This phenomenon is the problem of proving "complexity lower bounds". Lower bounds are among the great scientific mysteries of our time: there are many mathematical conjectures and beliefs about lower bounds---indeed, the security of the Internet and cryptography relies on such conjectures being true---but concrete results are few. The major goal of this project is to leverage humanity's vast knowledge of computer algorithms to prove new lower bounds: put another way, the goal is to use the power of computers to prove limitations on them. A secondary goal is to study the scientific consequences of these connections. It is hard to overestimate the potential impact---societal, scientific, and otherwise---of a theoretical framework which would lead to a fine-grained understanding of what computers can and cannot do. Another goal of the project is to bring complexity research closer to real-world computing, and to introduce practitioners to aspects of complexity that will impact their work. A final goal is educational outreach, through online forums dedicated to learning computer science and collaboration with the media on communicating theoretical computer science to the public.To give one example of a lower bound, a central question in computer science is the famous P versus NP open problem, which is about the difficulty of combinatorial problems which admit short solutions. Such problems can always be solved via brute force, trying all possible solutions. Can brute force always be replaced with a cleverer search method? This question is a major one; no satisfactory answers are known, and concrete answers seem far away. The conventional wisdom is that in general, brute force cannot be entirely avoided, but it is still mathematically possible that most natural search problems can be solved extremely rapidly, without any brute force. The mathematical theory is hampered by negative results showing that most known proof methods are incapable of proving strong lower bounds. A primary objective of this project is to help discover and develop new ways of thinking that will demystify lower bounds, and elucidate the limits and possibilities of computing. The major hypothesis of this project is that an algorithmic perspective on lower bounds is the key: for example, an earlier project led by the same research team shows that algorithms for the circuit-satisfiability problem (which slightly beat brute force search) imply circuit-complexity lower bounds. Other algorithmic problems, such as estimating the acceptance probability of a circuit without using randomness, and finding "bad" inputs which prove that a piece of code does not correctly compute a function, also turn out to be useful for proving lower bounds. The potential scientific applications are vast, ranging from logical circuit design, to network algorithms, to improved hardware and software testing, to better nearest-neighbor search (with its own applications in computer vision, DNA sequencing, and machine learning), and to cryptography and security.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.