权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Structure vs Randomness in Algorithms and Computation

算法和计算中的结构与随机性

基本信息

批准号：
EP/V048201/1
负责人：
Rahul Santhanam
金额：
$ 25.65万
依托单位：
University of Oxford
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2021
资助国家：
英国
起止时间：
2021 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FV048201%2F1
关键词：
Structure vs Randomness Algorithms 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.

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