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.