Structure vs Randomness in Algorithms and Computation

点击翻译按钮获取中文摘要

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.