Towards a Unified Theory of Proof and Circuit Complexity

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

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.