A single mathematical question—whether P equals NP—determines whether certain problems are fundamentally impossible for computers to solve efficiently, no matter how fast future hardware becomes. This project tackles that question by studying Boolean circuits, simplified models of computation made of logic gates. Researchers have long known that proving certain problems cannot be solved by small circuits would settle the P vs. NP question. But such impossibility proofs have a paradoxical side effect: they often turn into powerful algorithms themselves, useful for breaking cryptographic systems or training machine learning models. The project aims to strengthen this two-way street between impossibility proofs and practical algorithms. If successful, the work could refute recently proposed cryptographic schemes that rely on the assumption that certain circuits are hard to break. It could also produce new learning algorithms for neural networks and deepen understanding of quantum computing’s limits. The research is fundamental—it will not directly change a piece of software or a device tomorrow. But past work in this area has yielded unexpected breakthroughs in cryptography and combinatorics, and a definitive answer to P vs. NP would reshape the foundations of computing, security, and optimisation.
View original technical description
Counted among the 7 Clay Millenium Prize problems, the P vs. NP problem is one of the most influential unsolved problems of mathematics, with far-reaching implications for biology, cryptography, operations research, and many other fields. At heart, this question is concerned with the inherent mathematical limits of computational devices. If P = NP, then incredible algorithms are possible, though this also means that several real-world cryptographic systems are insecure. It is however widely believed that P is not equal to NP, and proving this conjecture amounts to a proof that it is impossible to design efficient algorithms for certain problems. The main purpose of the project is to make progress into such "proofs of algorithmic impossibility", while leveraging and further developing the apparently paradoxical phenomenon that such proofs often embed algorithms into themselves. One of the most promising approaches to solve the P vs NP problem is via Boolean circuits, a mathematical abstraction that captures the essential computational capabilities of everyday digital circuits. Circuits model computation as a sequence of simple, local steps, called gates, and the efficiency of the circuit is measured by its size (number of gates). Circuit lower bounds are an impossibility result which shows that no circuit of small size can solve a concrete problem of interest. A sufficiently strong circuit lower bound is enough to conclude that P is not equal to NP, solving the question. Most of the success in the investigation of circuits has been on restricted circuit models. Such models provide a precise mathematical formalism of specific types of algorithms, allowing us to investigate their power and limitations en-route to understanding computation at large. Along the years, this study has unveiled a beautiful synergy between circuits, mathematics, and algorithms. First, many proofs of circuit lower bounds have both drawn from and contributed to extremal and probabilistic combinatorics, with insights from lower bounds proving useful in recent breakthroughs in combinatorics. Second, such combinatorial proofs could often be transformed into highly impactful algorithms such as cryptographic attacks and learning algorithms, which could not be obtained otherwise. Finally, algorithms themselves have been employed to obtain new circuit lower bounds. The project will exploit and strengthen the above synergies in order to make progress in major questions in circuit complexity, algorithm design, and the theories of cryptography and learning, by means of the following objectives: I. Frontier circuit lower bounds: To develop methods based on combinatorics and discrete analysis to solve longstanding open questions in circuit complexity. This includes attacking the ACC0 vs. NP problem, a necessary step towards P is not equal to NP, and showing an exponential monotone circuit lower bound for Perfect Matching. II. Lower bounds for algorithms: To strengthen the algorithmic consequences of proofs of lower bounds, applying modern combinatorial constructions. Besides new learning algorithms, this direction can refute certain heuristic cryptographic constructions which were recently proposed. This includes learning algorithms for depth-2 neural networks, and algorithmic consequences of graph and communication complexity lower bounds. III. A theory of quantum algorithmic complexity: To develop the above synergies in the context of quantum computing, a very timely investigation in view of the rise of quantum cryptography. This includes circuit lower bounds from quantum algorithms, quantum learning algorithms from quantum cryptographic attacks for restricted quantum circuits, and complexity-theoretic characterisations of quantum cryptography and advantage.
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