Et is a huge problem, sometimes it is even considered the most important puzzle in contemporary computer science – and a German may have solved it now. The so-called P-NP conjecture is one of a total of seven millennium problems for the solution of which the American Clay Mathematics Institute offered a million-dollar prize 17 years ago. Since then there have been more than 100 proof attempts, all of which ultimately failed.
Now the computer scientist Norbert Blum, who teaches at the University of Bonn, has presented and published a proof that should finally solve the riddle. It’s 38 pages long, full of challenging mathematics, and simply titled “A Solution of the P versus NP Problem” (Click here to contribute).
How fast can computers solve a problem?
Its publication quickly made the rounds. Stanford professor of artificial intelligence and AI entrepreneur Reza Zadeh asked via the short message service Twitter: “Has anyone found an error in the P !=NP proof that Norbert Blum claims?” Norbert’s previous work has been great.”
Put simply, behind the puzzle is the question of how quickly or efficiently computers can solve a problem of a certain level of difficulty (complexity). Computer scientists distinguish between so-called P-problems (P stands for the term polynomial) and NP-problems, which, to put it simply, are more difficult or even unsolvable – and which a computer cannot solve efficiently. There is speculation that the two eventually merge into one another: NP problems can ultimately be broken down into a series of P problems – and can therefore be solved efficiently.
The question is currently highly explosive. Basically, the hope for modern encryption (cryptography) stands or falls with it. Some of the encryption codes currently in use are already considered NP problems, i.e. cannot be solved efficiently. Basically, if they were P-problems, that would mean that it’s only a matter of time before computers are able to crack them all efficiently. This is how the American physicist Scott Aaronsen assesses it, for example.
In his argument, Blum now comes to a conclusion that should make things easier for many computer scientists – namely that P is not the same as NP, i.e. that important encryption processes are not about to be fundamentally overturned. Experts had previously tended to assume this result, but they were unable to prove it.
Whether that is the case remains to be seen. Because even before Blum, many experts made such an attempt. Physicist Aaronson has set an incentive to examine Blum’s proof closely. He has announced in his blog that he would bet $200,000 on it, that Blum’s proof also contains an error. Let’s see.