The MATH+ Cluster of Excellence at FU, HU, and TU Berlin as well as Weierstraß and Zuse Institute is hosting an event on 1 July at the Futurium in Berlin as part of a national program titled “The 7 Greatest Mathematical Adventures.” The event at the Futurium celebrates the “P versus NP” Millennium Problem. In an interview, the man behind the project, Professor Dr. Martin Skutella from TU Berlin, explains why solving this problem can also impact our everyday lives and why this conundrum reveals a fundamental asymmetry between Yes and No.
Firstly, because it fits in well with what we do here in Berlin. It is an aspect of mathematics that deals with very specific applications. These could include, for example, how the BVG, the city’s public transportation company, could improve the organization of its schedules. This link to practical applications is an important aspect of mathematics research in Berlin. Also, the problem may sound complicated, but in reality, it is something a child can actually fairly easily understand.
Right. There is a certain set of problems where you can easily verify if a solution is correct. Let’s take a combination lock as an example. If someone tells me the code is “3,4,7,1” I can easily try this out and see if the lock opens. In complexity theory, we refer to the set of such problems as “NP.” Then there is a subset of NP, which we call “P.” This refers to problems which are easy to verify and also relatively easy to solve. Cracking the code for a combination lock does not belong to this set of problems. But let’s consider the example of a police file with thousands of fingerprints. If I have a fingerprint from a crime scene and then want to check if we have a record of this fingerprint on file, I can use a search algorithm. In just a few seconds I will have a result - so here the solution is easy to find. I can then manually compare the print found by the algorithm with that from the crime scene and verify if they really are the same.
The big question is if the two sets are perhaps identical. In other words, are all problems that are easy to verify also easy to solve? Perhaps we have simply not yet found the efficient solution for the problems in the NP set that seem difficult to us, which would then also make them elements of P. If this were the case, we would be able to say P = NP.
Yes, assuming the problem is such that I could easily check the solution. One of the things I work with are so-called approximation algorithms for difficult problems. Here, we always “only” find suboptimal solutions for practical applications. But we can sometimes prove mathematically that these suboptimal solutions are as close to optimal solutions as we can achieve. But I always have to write underneath “Unless P = NP.” It's an annoying detail and one we’ve had to deal with for decades now....
Oh, but it is! For one thing, P = NP would have extreme consequences for encryption technology, including also for our everyday life using debit cards and so on. Until now, this technique has been based on the fact that there are mathematical problems that have the functionality of key and lock, in other words with solutions that can be easily verified and are therefore in NP. But you can make these problems sufficiently difficult to prevent outsiders from cracking them even using the best computers - in other words they are not in P. This is the only reason why encryption is secure. But if the P set were identical with the NP set, there would have to be an easy-to-open backdoor, so to speak, for all those tasks so far considered uncrackable. In theory at least.
And there is a further twist. To prove that P = NP, you would only have to find a simple algorithm for just one difficult problem in NP. Let’s consider the Hamilton Circuit Problem. For example, in a railroad network a sequence for visiting several places is to be chosen such that no station except the first is visited more than once. You may also know this as the Traveling Salesperson Problem. In any case, it was possible to show that all the problems in NP which until now had appeared difficult to us - and there are thousands of them! - are related to each other. So, if I were able to find a simple algorithm for just one of the problems, I would only have to adapt this for the others and I would have solved them all in one fell swoop. This is precisely why so many amateur mathematicians are interested in the P versus NP conundrum.
By easy I mean tasks that do not require a huge increase in the time required to solve them if I make them bigger, such as if I want to optimize 2000 bus stops rather than 1000 in the BVG timetable. Mathematicians talk of a polynomial solution in this context. A difficult problem would be one whose solution time increases exponentially as the number of bus stops increases. All problems which can only be solved by trial and error are examples of difficult problems.
Blum is a genuine expert in the field. And unlike many others, he wasn’t looking to prove that P = NP - the opposite in fact, namely that the P set and NP set are not the same. Incidentally, this is also precisely what most mathematicians and computer scientists assume to be the case. Unfortunately, it soon became apparent that there was a flaw in his reasoning.
Yes, I think I can do that. To understand, you only need to know that I can convert any algorithm into a logic circuit for a computer chip. To do this, I have to trace it back to the three logical building blocks for zeros and ones that computers work with. Two of these are the AND and the OR gate. These always have two inputs and one output. Two ones must arrive at the AND gate so that it also exports a one at the output. With the OR gate, a one on one of the inputs is sufficient for this. Then there is the NOT gate which has just one input and one output and simply reverses the entry signal: A one becomes a zero and a zero becomes a one.
We have long known that this NOT gate is essential if the computing time for solving a problem is not to increase exorbitantly as the size of the problem increases, such as in the case of the number of bus stops. Such efficient solutions are then in P. And Blum wanted to show that if there were an efficient solution for every difficult problem in NP, i.e. if P = NP, then there would also have to be a solution that functions without the NOT gate. And that would contradict the proven result which says that the NOT gate is absolutely essential for efficient solutions. Ergo, P = NP must be false.
Yes, indeed. The proof is 38 pages long and contains in principle so-called Boolean algebra, which works with these logical operators. By the way, this is something some people also learn in school and can be used very well to solve logical puzzles.
Right. Incidentally, there is also a deep, almost philosophical aspect connected to the “P versus NP” conundrum. This also has to do with the NOT, which apparently distinguishes P from NP and, yes, swaps 1's and 0's, or Yes and No. With the verifiability of solutions required in the NP set, there is now obviously an imbalance between yes and no, an asymmetry. Let’s take the example of the combination lock again. If you set someone a task to “construct a lock with at least one solution,” then this person can immediately demonstrate that they have fulfilled the task by opening the lock with the combination “3,4,7,1”. But if you set the person the task to “construct a lock with no solution,” in other words effectively a negation, then you can only verify if the task has been fulfilled by trying out all possible number combinations over a long period of time.
This is the same as in real life. If someone asks me “Can you do this or that?” then I can say yes and I can do it. But if I say no, how should I ever prove that I really can’t do it and that I am not just being lazy?
Interview: Wolfgang Richter