Limits of Symmetric Computation

对称计算的限制

• 批准号: EP/X028259/1
• 负责人: Anuj Dawar
• 金额: $ 270.38万
• 依托单位: University of Cambridge
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2023
• 资助国家: 英国
• 起止时间: 2023 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX028259%2F1
• 关键词: Limits; Symmetric; Computation

The problem of separating the complexity classes P and NP is a central open question in theoretical computer science and one of the most famous open problems in all of mathematics. While a vast field of research in computational complexity has developed around it, we do not as of now have any credible research agenda that offers an approach to this problem. In order to prove super-polynomial lower bounds for NP-hard search problems, we need three ingredients: (1) A classification of structure in search spaces; (2) A classification of polynomial-time algorithms; (3) Mathematical tools for dealing with these. There have been recent developments in theoretical computer science that have advanced our understanding on the first two. The dichotomy theorem for constraint satisfaction problems provides a thorough classification of search spaces for one collection of well-behaved problems, and the developing theory of symmetric computation reveals fundamental limitations of some polynomial-time algorithms, spanning circuit complexity, combinatorial optimization and hardness of approximation. In this project we exploit a striking convergence of these two to obtain further groundbreaking results. We aim at a complete classification of constraint solving algorithms by the symmetries they preserve. We propose a sweeping re-evaluation of the foundations of algorithmic complexity in the light of symmetry. The theory of symmetric computation that will be developed will yield new lower bounds in circuit complexity and approximability as well as new insights into the graph isomorphism problem. This will build on tools from a number of mathematical areas - representation theory, algebraic topology and category theory.

分离复杂性类P和NP的问题是理论计算机科学中的一个中心开放问题，也是所有数学中最著名的开放问题之一。虽然计算复杂性的研究领域已经围绕着它发展起来，但到目前为止，我们还没有任何可信的研究议程来提供解决这个问题的方法。为了证明NP难搜索问题的超多项式下界，我们需要三个要素：（1）搜索空间中结构的分类;（2）多项式时间算法的分类;（3）处理这些问题的数学工具。理论计算机科学的最新发展促进了我们对前两个问题的理解。约束满足问题的二分法为一组性能良好的问题提供了一个彻底的搜索空间分类，而对称计算理论的发展揭示了一些多项式时间算法的基本局限性，跨越电路的复杂性，组合优化和近似的困难。在这个项目中，我们利用这两个惊人的收敛，以获得进一步的突破性成果。我们的目标是在一个完整的分类约束求解算法的对称性，他们保持。我们提出了一个全面的重新评估的基础上的算法复杂性的对称性。对称计算理论的发展将产生新的下限电路的复杂性和近似性，以及新的见解图同构问题。这将建立在一些数学领域的工具-表示理论，代数拓扑和范畴理论。