Limits of Symmetric Computation

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

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.