Towards a Unified Theory of Proof and Circuit Complexity

走向证明和电路复杂性的统一理论

• 批准号: RGPIN-2021-03036
• 负责人: Robere, Robert
• 金额: $ 3.35万
• 依托单位: McGill University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750379
• 关键词: Towards; Unified; Theory; Proof; Circuit

Consider the following problem: you are given an extremely large (say, 10,000 digit) number, and are asked to find any number (other than 1 or itself) that divides it. This problem is, apparently, very hard for powerful computers to solve efficiently. Moreover, much of the technology of the modern world crucially relies on the fact that this problem is hard to solve, since its hardness is the foundation of the cryptography that keeps all of our internet communications safe! Such questions about the intrinsic hardness of computational tasks are the study of computational complexity theory, which is my area of research. In complexity theory, we study the amounts of resources --- like running time, memory, or energy --- that computers must consume to perform their computations. In this way, computational complexity is the flip side of the coin to algorithm design, which is concerned with finding the most efficient algorithms for a given task. This research proposal outlines a new and powerful family of techniques --- called lifting theorems --- that have been developed in computational complexity theory. These new techniques have had a dazzling number of applications, leading to the resolution of a large number of hard problems in both computational complexity theory and discrete mathematics. Furthermore, they have revealed deep new connections between algorithms and proofs; showing that, in many cases of interests, algorithms are proofs and proofs are algorithms, and so analyzing one object allows us to analyze the other. The "lifting revolution" is far from being over and, in this proposal, we identify three concrete directions that we believe are ripe for attack with these new techniques. The first is deepening our understanding of algorithms commonly used in optimization; the second, in quantum computation; and the last, the theory of digital circuits (the same types of circuits that run your computer). Finally, we believe that a deeper --- and currently, only partially understood --- theory that explains the surprising breadth of these applications can also be developed, and indicate some promising work in this direction.

考虑以下问题：给您一个非常大的（例如10,000位）的数字，并被要求找到将其划分的任何数字（除1或自身以外）。显然，强大的计算机很难有效地解决这个问题。此外，现代世界的许多技术至关重要地依赖于难以解决的事实，因为它的硬度是密码学的基础，它可以确保我们所有的互联网通信安全！ 关于计算任务内在硬度的此类问题是计算复杂性理论的研究，这是我的研究领域。在复杂性理论中，我们研究了资源的数量 - 例如运行时间，内存或能量 - 计算机必须消耗执行其计算的资源。这样，计算复杂性就是硬币到算法设计的翻转侧，它与为给定任务找到最有效的算法有关。这项研究建议概述了一个新的强大技术系列 - 称为提升定理 - - 在计算复杂性理论中已经开发了。这些新技术具有大量的应用，导致在计算复杂性理论和离散数学中都解决了许多硬问题。此外，他们揭示了算法和证明之间的新联系。表明，在许多感兴趣的情况下，算法是证明和证明是算法，因此分析一个对象使我们能够分析另一个对象。 “提升革命”还远远没有结束，在这项提案中，我们确定了三个具体的方向，我们认为使用这些新技术已经成熟了。首先是加深我们对优化常用算法的理解。第二，在量子计算中；最后是数字电路理论（与计算机运行的相同类型的电路类型）。最后，我们认为，更深入的 - 目前，只有部分理解的---理论解释了这些应用的令人惊讶的广度，也可以开发出令人惊讶的广度，并在这个方向上表明了一些有希望的工作。