December 4 2025: Sudan's talk about P-NP Problem

Oliver Knill, December 5, 2025

About The Talk

The P-NP problem is definitely the most accessible problem form all the 7 Millenium problems. You do not have to be a mathematician to understand it. We all have seen problems that are hard and problems that are easy. It is also the problem where I would predict that the vast majority of mathematicians are convinced the answer negative. (There was a little kid even in the audience for Sudans talk and he seems have understood things perfectly well as he commented on the talk). The reason why the problem is so accessible because we all know easy and hard problems. An example of a difficult NP problem is the traveling salesmen problem. An other is mine sweeper. An example of an easy P problem is house of santa Klaus (and in general any problem dealing with Eulerian paths) or the 15 puzzle (easy decision problem based on the sign of a permutation). Sudan mentioned that it might be the last to be solved. Here is my take on difficulty of problems (mentioned on this youtube pressentation from 2 years ago for example): Problems are difficult if there is no theorem that simplifies it. Theorems produce insight and make problems easy. The Eulerian path problem is easy because of the Euler-Hierholzer theorem which started the entire biz of graph theory with the Koenigsberg problem. The Hamiltonian path problem is hard because there is no theorem giving whether a general graph is Hamiltonian or not. The Vertex arboricity problem is hard because there is no theorem, the Edge arboricity problem is easy because of the Nash-Williams theorem. A similar thing happens about whether a statement is true or not: also this I have mentioned before as a "personal guiding principle". If there is no reason for something to be true, it is false. This leads to the prediction that the Riemann hypthesis is likely to be false and that that the Collatz (3x+1)-problem is likely to be false (also there, the numerical evidence can be misleading). I wrote a bit more on my blog about personal predictions about the problems: (this has to be taken with a grain of salt of course because nobody can predict the future and even good mathematicians have done terrible predictions). But the short is that the "people problems" (Navier Stokes, Hodge, Riemann, Birch and Swinnerton-Dyer) will be solved in this century, that P-NP will turn out to be unprovable and that the Mass gap problem is unsolvable because it is a terrible question. The talk of Sudan was very good. I had learned about the complexity problems when they were still fresh in the 1980ies in Specker seminars almost 40 years ago and a lot of things have happened since. We had discussed Zero knowledege stuff in the 90ies heavily in cryptology group of military but the PCP theorem is a new thing for me.

Some Slides

Oliver Knill, Posted December 5, 2025