P-NP-PROBLEM : New attack on the biggest mystery of computer science

For decades, computer scientists argue whether the complexity classes P and NP are in fact identical. A German researcher will have answered the question. Now, computer scientists around the world are discussing his work.

It is considered the greatest mystery of modern computer science. The American computer expert Scott Aaronson considers it the

most profound question people have ever asked themselves.

Now the mathematics professor Norbert Blum from Bonn (Germany) has put a mathematical proof on the Internet, which is to solve the century problem. "A Solution of the P versus NP Problem" is 38 pages long, and it is difficult for the lay people to understand.

The one who finds a correct solution, besides the fame also beckons much money: The P-NP problem is one of the seven Millennium problems that the Clay Mathematics Institute has proposed in the year 2000 for a $ 1 million USD solution.

If Blum's now published argument is right, the scope would be enormous: the researcher believes that he can prove that P is not NP. This would be a disappointment for number researchers, a relief for cryptographers - and in any case a result for the history books.

The complexity is important

At the core of the P-NP problem is the question of how quickly a computer can solve certain tasks. Computer scientists here distinguish P-problems and NP-problems. P problems can be calculated in polynomial time. One could also say that the effort for the solution increases to a reasonable extent as the input to be calculated grows. Mathematically, this corresponds to the relation n^k, where n is the input length and k is a constant. One example is the question of whether a number with n digits is a prime number - this can be checked by modern algorithms with comparatively few computation steps.

The situation is different when the effort for solving a problem increases exponentially, as in scheme 2ⁿ. Such tasks are sometimes so extensive that they can no longer be solved by a computer within a reasonable amount of time. The complexity class NP is again a special case: it includes "non-deterministic polynomial" problems, which make computer scientists understand tasks that seem to grow rapidly with complexity through deterministic computers.

A computer is deterministic when it performs computation steps one at a time and can not try all possible solutions at once - in fact, all today's computers are deterministic. You can quickly check whether a solution is right for a NP problem. Finding the right solution sometimes requires a very long search, after all, a deterministic computer has to try all possible ways successively.

An extreme example of a NP problem is a travelling salesman who wants to visit a number of cities, but should be as short as possible. The number of possibilities that a computer has to check when calculating the shortest route grows at least exponentially with the number of cities to be visited. A nightmare for every machine. (In fact, the travelling salesman is so tricky that experts are talking about a NP-serious problem).

For mathematicians, a dream would burst

Perhaps, however, computer scientists are simply not taking on tasks like this: Is NP problems really a question that can be solved with tricks in polynomial computing time? If so, this would mean that P equals NP. The computer scientist thinks this is quite unlikely. The consequences would be enormous, however, because the cracking of common encryption codes is an NP problem. If this is really a P problem, it might be just a matter of time before computers take out many cryptographic procedures, writes Scott Aaronson in an analysis of the problem.

If the proof of Norbert Blum were correct, computer experts around the world could breathe a sigh of relief. For some mathematicians, on the other hand, a dream would burst: the search for mathematical evidence is also a NP problem. If P equals NP, you could easily find the solutions to some of the other million-dollar Millennium problems from a computer.

Whether this possibility ends with Blum's proof for all times must now be judged by other computer scientists and mathematicians. Some of them have already begun to examine the arguments of the scientist from Bonn.

This is one of the biggest problems of computer science at all, says Günter Rote, computer science professor at "Freie Universität Berlin" (Free University of Berlin).

Earlier evidence was simply incomprehensible

Initial assessments of Blum's proof have already surfaced on the Internet. The computer scientist Luca Trevisan from the University of California, Berkeley, believed the day after the publication about to have found an obvious mistake in the paper, but soon resigned. In a blog post, he now sketches Blum's evidence and lists a number of possible weaknesses of the argument. Soon one would know whether such objections are justified, writes Trevisan.

In other experts, the work left a good first impression:

Has anyone found a mistake in the proof? Norbert's last work was great, commented the computer researcher Reza Zadeh from Stanford University on Twitter.

An anonymous user of the "Theoretical Computer Science Stack Exchange", on the other hand, noted that the paper was written well enough to be either right or wrong. The blown work of many P-NP-proofs of the past, which were simply incomprehensible.

To this Rote agrees:

If you look through the proof, it does not look very deterrent, but as if you could understand it without much effort.

Blum essentially uses mathematical concepts, which have been known for ten years - and are therefore considered to be tested.

There are already 116 proofs to P-NP

For some experts this is a reason to doubt the work of the researcher. Such a big problem as P-NP is probably solved by surprising new gimmicks and not by a modification of well-known recipes, the mathematician Alon Amit suspected on the platform "Quora". Blum's approach is similar to that of two Scandinavian computer scientists from 1999.

In the meantime, Scott Aaronson has also spoken out, who is an authority in the matter of P-NP. He is betting $ 200,000 on the fact that the evidence, like all previous attempts, is flawed, the computer scientist wrote from the University of Texas in Austin on his blog.

In fact, in the past, some scientists have presented evidence of the famous computer science problem. Gerhard J. Woeginger from the RWTH Aachen has listed all previous attempts and comes to a total of 116 attempts. They all turned out to be wrong.

Blum himself does not want to express himself to his proof. He wanted to wait and see what his colleagues say to his work.

He likes to delve into difficult problems and solve them alone, says the Berlin computer scientist Günter Rote about his colleagues from Bonn.

Normally the circle of people who critically examine Blum's work should be manageable. This time, however, he has created a problem that fascinates computer experts around the world. How their final conclusion will turn out is currently still open.