Structure vs Randomness in Algorithms and Computation

P与NP问题是指是否所有具有有效可验证解的计算问题都是有效可解的。这是数学中尚未解决的主要问题之一，不仅与数学和计算机科学有关，而且与物理学、生物学和经济学等领域有关。从根本上讲，P与NP问题是关于计算问题的有效算法的可能性和局限性。通过对几个中心问题的计算难解性进行假设，发展了一个有用的计算复杂性理论。然而，在没有这些假设的情况下，人们对算法知之甚少。每个计算问题都有一个巨大的潜在算法空间，在不假设手头的问题没有快速算法的情况下，这是一项具有挑战性的任务。我们的研究目标是从基本原理出发，在不假设某些问题是棘手的情况下，提高我们对算法和计算的知识。这种关于计算问题复杂性的无条件结果在一些受限的设置中是已知的，但在理解更具表现力的计算设备和算法的局限性方面进展缓慢。大多数现有下限技术的障碍已经被识别，新的方法似乎是在这一领域取得实质性进展所必需的。为了实现这一点，我们建议探索一种基于结构和随机性之间的二分法的新的计算视角。“结构”指的是有一种(也许是意想不到的)方法来有效地解决某个计算问题。相反，“随机”指的是快速算法表现出伪随机行为的情况，即，尽管确定性的行为不能通过任何有效的测试从随机中区分出来。结构和随机性之间的二分法表明，计算情况要么是结构化的，要么是随机的。假设我们希望使用结构-随机性二分法来展示一个关于计算复杂性的新结果。关键是找出“结构”和“随机性”的正确概念，以便我们能够展示结构-随机性的二分法，并且能够表明期望的结果在结构化情况下和在随机情况下都成立。然后，从结构-随机性二分法得出，期望的算法结果无条件地成立。请注意，这种方法具有非常吸引人的特点，即我们不需要知道问题的可能算法的大空间是“结构化的”还是“随机的”；因此，我们能够巧妙地解决前面讨论的困难，因为我们对算法可以做什么或不能做什么的理解有限。我们的方法是跨学科的，结合了算法、复杂性理论和数理逻辑的见解。我们计划利用结构和随机性的二分法来给出新的：(I)算法结果，(Ii)在P和NP上取得进展的复杂性下界，(Iii)形式独立性结果，指出复杂性下界不能在受限的数学理论中得到证明，例如Peano Arithmetic的片段。对于这些方向中的每一个，都有基于初步观察和对先前工作的重新解释的证据表明，结构对随机性方法可以是卓有成效的。这个项目将对这一范例进行系统的应用，以调查这些问题，并有可能从根本上影响我们对算法和计算复杂性的理解。

The P vs NP problem asks whether all computational problems with efficiently verifiable solutions are efficiently solvable. This is one of the major unsolved problems in mathematics, and has relevance not just to mathematics and computer science but also to physics, biology and economics, among other areas. Fundamentally, the P vs NP problem is about the possibilities and limitations of efficient algorithms for computational problems.A useful theory of computational complexity has been developed by making assumptions about the computational intractability of a few central problems. However, little is known about algorithms without such assumptions. There is a vast space of potential algorithms for each computational problem, and showing without an assumption that there is no fast algorithm for the problem in hand is a challenging task.Our goal in this research is to advance our knowledge of algorithms and computation from first principles and without assuming that certain problems are intractable. Such unconditional results on the complexity of computational problems are known in some restricted settings, but progress in understanding the limitations of more expressive computing devices and algorithms has been slow. Barriers to most existing lower bound techniques have been identified, and novel approaches appear to be necessary to achieve substantial advances in this area.In order to achieve this, we propose to explore a novel computational perspective based on dichotomies between "structure" and "randomness". "Structure" refers to a situation where there is a (perhaps unexpected) way to solve a certain computational problem efficiently. In contrast, "random" refers to a situation where fast algorithms exhibit pseudorandom behaviour, i.e., behaviour that though deterministic cannot be distinguished from random by any efficient test. A dichotomy between structure and randomness states that either a computational situation is structured or it is random.Suppose we wish to show a new result about the complexity of computations using structure-randomness dichotomies. The key is to identify the right notions of "structure" and "randomness" so that we are able to show a structure-randomness dichotomy, and moreover are able to show that the desired result holds both in a structured situation and in a random one. It then follows from the structure-randomness dichotomy that the desired algorithmic result holds unconditionally. Note that this approach has the very appealing feature that we do not need to know whether the large space of possible algorithms for a problem is "structured" or "random"; thus we are able to finesse the difficulty discussed earlier regarding our limited understanding of what algorithms can or cannot do.Our approach is interdisciplinary and combines insights from algorithms, complexity theory, and mathematical logic. We plan to exploit structure versus randomness dichotomies to give new:(i) algorithmic results,(ii) complexity lower bounds that make progress on P vs NP,(iii) formal independence results stating that complexity lower bounds cannot be proven in restricted mathematical theories, such as fragments of Peano Arithmetic.For each of these directions, there is evidence based on preliminary observations and reinterpretation of previous work that a structure vs randomness approach can be fruitful. This project will perform a systematic application of this paradigm to investigate these questions, with potential to impact in fundamental ways our understanding of algorithms and computational complexity.