AF: Small: Lower Bounds in Complexity Theory Via Algorithms

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

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.