A single, unsolved question in computer science—whether problems that are easy to check are also easy to solve—has stumped mathematicians for over fifty years, and this project aims to crack it by studying the hidden symmetries inside algorithms. The P versus NP problem asks whether every problem whose answer can be verified quickly can also be solved quickly. A proof either way would reshape everything from cryptography to logistics, but no one has a credible strategy for tackling it. This project offers one. The researchers will classify polynomial-time algorithms by the symmetries they preserve—a mathematical property that limits what they can compute. By combining recent breakthroughs in constraint satisfaction and symmetric computation, they aim to prove that certain hard problems truly cannot be solved efficiently. If successful, this would settle a foundational question in mathematics and computer science. It would also yield new lower bounds in circuit design and approximation algorithms, and deepen understanding of the graph isomorphism problem—a puzzle with implications for network analysis and database search. The work is fundamental science: it does not promise a new app or a faster chip. But like group theory before it, a deeper grasp of symmetry in computation could quietly reshape the logical architecture that underpins modern software.
View original technical description
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.
Plain English summaries and category classifications on this site are generated by AI and may not perfectly reflect the original research.
Is something wrong? Let us know