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 Open问题，这是关于组合问题的难度，这些问题允许使用简短的解决方案。这些问题始终可以通过蛮力来解决所有可能的解决方案。蛮力能否始终用更聪明的搜索方法代替？这个问题是一个主要问题。尚无令人满意的答案，具体的答案似乎很远。传统的观点是，通常无法完全避免蛮力，但是在数学上仍然有可能在没有任何蛮力的情况下非常迅速地解决大多数自然搜索问题。数学理论受到负面结果的阻碍，表明大多数已知的证明方法无法证明强大的下限。该项目的主要目的是帮助发现和开发新的思维方式，这些思维方式将使下限揭开下限，并阐明计算的限制和可能性。该项目的主要假设是，对下限的算法观点是关键：例如，由同一研究团队领导的较早项目表明，电路可满足性问题的算法（略微击败了蛮力搜索）意味着电路复杂性降低了速度。其他算法问题，例如在不使用随机性的情况下估算电路的接受概率，并找到证明一块代码无法正确计算功能的“不良”输入，也证明对下限也很有用。潜在的科学应用是广泛的，从逻辑电路设计到网络算法，改进了硬件和软件测试，再到最近的最近邻居搜索（在计算机视觉，DNA测序和机器学习中使用其自己的应用），以及加密和安全性，再到NSF的法定任务和审查的范围，这表明了审查的范围，这是通过评估的范围来进行的。