AF: Small: Lower Bounds in Complexity Theory Via Algorithms

AF：小：通过算法实现复杂性理论的下界

基本信息

批准号：
2127597
负责人：
Ryan Williams
金额：
$ 50万
依托单位：
Massachusetts Institute of Technology
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2021
资助国家：
美国
起止时间：
2021-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2127597&HistoricalAwards=false
关键词：
AF Small Lower Bounds Complexity

项目摘要

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.

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