Madhu Sudan | The P vs. NP problem: An Existential Question for Mathematics

Millennium Prize Problems Lecture 12/3/2025 Speaker: Madhu Sudan, Harvard University Title: The P vs. NP problem: An Existential Question for Mathematics Abstract: At the beginning of the twentieth century, in response to questions raised by Hilbert, illustrious mathematicians such as Godel, Church and Turing formalized the notion of theorems and proofs. Proofs were automatically verifiable while theorems are logical propositions for which proofs exist. The formal definition of a computer, a definition that had strong influence on the later development of the technology, was a by-product of the effort to define the phrase “automatically verifiable”! While the resulting theory had major implications already, one notion was however missing in the early definitions. Proofs were meant to be easily verifiable, while determining the truth of a proposition/conjecture (arguably a core task of mathematics) was not necessarily so. But what is “easiness” and how is it to be defined? While this was already hinted at by Godel in the 50s, the notion was finally formalized in seminal works of Cook, Levin and Karp in the early 70s. Central notions here included the adoption of the notion that polynomial time algorithms are (the only) tractable ones, and the realization that algorithms seeking to remove the existential quantifier in the definition of a “theorem” lead naively to exponential time algorithms. But are there no sophisticated algorithms to search for proofs? This is the profound “Is P = NP?” question. In this talk we will introduce the question and explain implications of resolutions of this question to the modern computing infrastructure, to mathematics and other sciences. We will briefly describe the state of progress on this question and recent progress on weaker forms of this question. Finally we will also aim to connect this question, and why one may believe that P != NP (proof search can not be automated) even in the face of accumulating evidence on the ability of computers to solve more and more complex mathematical problems, which seem to implement brute force search in less than polynomial time.