The world of theoretical computer science has been turned upside down by a stunning triple development which has finally solved its most famous problem: whether P=NP. This was one of the seven problems for which the Clay Mathematics Institute offered a million dollars in their famous Millennium Meeting over thirty years ago, and the second (after the Poincaré conjecture) to be solved. However, a controversy has erupted over how the prize money (which ten years ago was increased to two million dollars) should be distributed.
What does the statement `P=NP' mean? A good way to understand it is to look at an illustrative example. Suppose I secretly choose two prime numbers p and q, tell you their product n=pq and ask you to tell me what p and q are. In principle you can work this out, since by the fundamental theorem of arithmetic p and q are uniquely determined. However, in practice it is not easy to come up with a systematic way of finding them other than to look at all primes up to n1/2 and see whether they are factors of n. If n has 500 digits, this takes much too long to be feasible on even the fastest computers, and this difficulty is the basis of much of modern cryptography. Actually, more efficient methods have been discovered than straightforward trial and error, but, even after decades of intensive research, it is still out of the question to factorize a 500-digit number. At the end of the last century there was a great deal of excitement when Peter Shor discovered that quantum computers could factorize large numbers far more efficiently, but, despite several well-publicized announcements to the contrary, nobody has managed to build such a computer.
However one looks at it then, factorizing large numbers is not easy. However, the following related problem is much much easier: I choose p, q and n and ask you whether n=pq. All you have to do to answer this problem is a boring long multiplication, and if you are careful, or use a computer, you can do this quickly and accurately. Thus, although it looks hard to find p and q, it is much easier to check whether pq=n once p and q have been found.
There are many other problems in computer science of a similar nature. They ask you to find an object with certain properties, and while this looks extremely hard, it is easy to check whether a given object has the required properties. One interesting example is the following: I give you a mathematical statement S and ask you to find a proof of S of under a certain length (written in a formal language of your choice). One of the great fascinations of mathematics is that it is (in principle anyway) far easier to check whether a proof is correct than it is to find the proof in the first place.
The statement `P=NP' is roughly speaking the extraordinary claim that when a property is easy to check, it is also easy to determine whether any object has the property. Thus, if P=NP, then from the fact that long multiplication is easy it would follow that factorizing large numbers was easy, and from the fact that proofs are easy to check it would follow that they are easy to find. Despite the strongly counterintuitive nature of these conclusions, they are now known to be true - but with qualifications which will be described below.
As mentioned above, this breakthrough came in three stages. First, in a little known paper of 2019, Yuri Kolpakov, a Russian topologist, found a higher-dimensional generalization of Frank's celebrated knot-untying algorithm of three years earlier. Following Frank's general scheme, Kolpakov showed that, given a hypersurface in Rn, one could associate with it a graph with edge-weights belonging to a certain ring. It was then possible to prove that the hypersurface was knotted if and only if the graph had a property which, by a generalization of classical results of Robertson and Seymour, was equivalent to the non-existence of certain weighted subgraphs known as forbidden proper minors. Testing for these can be done in polynomial time.
The technical details need not concern us here, but one point is worth noting. The proof of Robertson and Seymour does not actually provide the forbidden minors: it merely proves indirectly that they exist. The same applies to the generalization. Consequently, Kolpakov's proof, like Frank's before him, does not actually give any bound on the degree of the polynomial which itself bounds the time taken by his algorithm.
The second step was made two years ago by Jane Nichols, a graph theorist at Yale. She was studying the computational complexity of certain problems in graph theory, and while doing so discovered a complicated property of graphs, again with weights in certain rings, which she called, ironically in the light of later developments, `pseudo-twistedness'. She showed that this property was NP-complete. This, in brief, means that if an efficient algorithm could be found for discovering whether a graph was pseudo-twisted, then P would equal NP. Like almost everybody else, Nichols took this as convincing evidence that detecting pseudo-twistedness was intractable, and moved on to other research. Her paper also received little attention, and it is interesting to speculate why this was. It has been suggested that the phrase `pseudo-twisted' was somehow off-putting to most mathematicians, causing them to believe that Nichols's research was not well motivated, though in a recent paper, she has explained the very interesting line of thought, originating in theoretical physics, that led her to her definition.
Nichols gave several talks on her work, including a colloquium at MIT, which was attended by Mike Stearns, a young topologist who had been studying the work of Kolpakov. As he put it later:
As the talk progressed, an idly outrageous thought occurred to me - wouldn't it be amusing if Kolpakov's untwisting algorithm could detect Nichols pseudo-twistedness of graphs? At first I chuckled inwardly - but then I began to feel the hairs on the back of my neck standing on end. I skipped the tea after the talk and rushed back to my apartment, where I stayed until I more or less collapsed into bed at 4am. I got up the next morning feeling totally sure that there must be a mistake, but everything seemed to check out.
What Stearns had done was to find a `polynomial reduction' from Nichols's problem to Kolpakov's. That is, in effect he devised an efficient algorithm for transforming a graph into a high-dimensional analogue of a knot diagram, in such a way that the graph was pseudo-twisted if and only if the `knot diagram' was genuinely knotted. Kolpakov's powerful algorithm could thus be used to determine whether graphs were pseudo-twisted, even though this had been shown by Nichols to be an NP-complete problem.
Stearns's initial reaction was to go out and celebrate, but soon things were to turn sour.
At first I was disbelieving. Then, after a few days of careful checking, I convinced myself that the argument was sound. I then wrote it up quickly and asked one or two colleagues to check the details themselves. Unfortunately, word got out about what was going on, and I suddenly found myself at the receiving end of a whirlwind of attention, most of it unwelcome. People started to say that my contribution to the problem was trivial: essentially nothing more than putting two pre-existing pieces of work together. But if that was all it took, then why didn't Nichols solve the problem two years ago?
Here is Nichols's view of the matter.
Yes, Stearns deserves credit for noticing that Kolpakov and I had, between us, proved that P=NP, but no, his reduction is not a difficult piece of mathematics. The way I like to look at it, the proof that P=NP comes in two parts, Kolpakov's polynomial-time algorithm and my proof of NP-completeness. It is not quite trivial that these apply to equivalent problems, and I fully admit that I did not recognise the importance of what I had done. Nevertheless, I think Stearns's achievement was one that would have been made by whoever was the first person to think of trying it. Certainly, as soon as I heard what he had done, I was able to come up with a reduction myself without seeing his preprint.
Don Jackson, one of Stearns's colleagues at MIT, hotly disputes this version of events.
Nichols is understandably bitter that she was not the person who solved the P=NP problem. However, the fact remains that if Stearns had not existed, then it would almost certainly still be unsolved today. Sometimes in mathematics, it is not the technical achievement that matters, but the courage and vision to ask the big questions.
What of Kolpakov? He has been keeping his own counsel so far, but one can well imagine his reaction at hearing that he is likely to share a prize of two million dollars. The decision about how to split the money is made by the scientific committee of the Clay Mathematics Institute. When we contacted a representative yesterday, she said:
The prize will not be awarded until the result is published in a reputable journal, and a committee, which is yet to be formed, has deemed it to be correct. This process will take at least two years, and until then the Institute has no comment about how the prize will be shared.
Leaving aside the question of the exact apportioning of credit, and surely all three mathematicians deserve our huge admiration for this remarkable achievement, what is the significance for mathematics and computer science? Here again there is a wide divergence of opinion. Jim Davies, a computer scientist at Stanford, believes that the importance of the P=NP problem has been exaggerated.
So there's a polynomial time algorithm for factorizing integers, proving theorems, finding Hamilton cycles etc. And then what? The degree is not just large, it is unknown. Probably if it was known then it would be enormous. Even an n10 algorithm is useless for practical purposes. So nobody's going to be put out of business just yet.
Don Jackson disagrees.
This is the beginning of the end. Even if the algorithm isn't practical, it delivers a shattering psychological blow to the mathematical community. We may still be better than computers at doing mathematics, but we are not that much better . In any case, now that the existence of an algorithm is known, the hunt is on for an explicit example. Historical precedent and the enormous commercial implications of being able to solve NP-complete problems suggest that this story is set to run and run.
Only time will tell. Meanwhile, if you are struggling to prove a theorem, you'd better hurry up if you want to get there before some clever computer programmer does it first.