Explaining the P vs. NP conjecture – a different approach
The P vs. NP conjecture in complexity theory is one of the most prominent open problems in mathematics and computer science. There are many reasons for this. It is reasonably easy to get an intuitive idea of what it states, it has many deep implications for everyday life in both science and society. Last but not least, there is a million-dollar prize, the Clay Mathematics Institute, offered to the one to finally solve it. Naturally, this inclusion to the selected group of Millennium Problems confirms the importance of the conjecture. However, throughout the years, it turned out to be a tough brain twister, a hard nut to crack for the most distinguished scientists in the area and there is still no solution in sight.
Being such an important issue among mathematicians, it undoubtedly is of significance to share and explain the meaning of the P vs. NP conjecture to the non-mathematical society. In this context, I hoped to find different and appealing ways to describe the conjecture. Looking for ideas, during the 7th Heidelberg Laureate Forum in 2019 I had a very interesting conversation with Stephen Cook – the father of this conjecture. Here I would like to share my personal conclusions on how to visually describe the conjecture. There will be an open problem for the reader at the end. 🙂
First, and perhaps in contradiction to the motivation of this article but ultimately necessary to ensure we are all on the same page, a brief description of what the P v. NP conjecture says. The conjecture is a statement about easy and difficult problems and how they are related. In mathematical language, we talk about classes, the P class and the NP class, which are both a collection of mathematical problems. One example of such a problem might be, “Given a group of cities and the distances between them, is there a way to visit each city once without traveling more than a given amount of km?” We say that the problem has a solution if there is an algorithm that describes a way of finding such a path. Naturally, the time the algorithm needs to obtain the solution will depend on the input, in this example on the number of cities you are considering. Some algorithms are more sensitive to size changes than others. The P class is the class of problems solvable in polynomial time, which means that the time the algorithm needs to find a solution can be expressed as a polynomial function, depending on the input size. We like these kinds of algorithms since they are not that sensitive to size changes and therefore we like these kinds of problems. Whenever we face a new problem, it is desired to find a polynomial time algorithm in order to include the problem in the P class. The NP class is a more general class. Here Cook makes an initial observation, explaining a common misconception: NP does not mean non-polynomial, which would be the opposite to the P class. NP stands for nondeterministic polynomial time and the class consists rather of all those problems for which we may not possess a polynomial time algorithm, but for which a positive answer to the question can be derived in polynomial time from a given certificate. In our example, if I give you a specific path that goes through all cities in less than the given amount of km, it would be quite straightforward to check that this path actually solves the problem: you confirm that the path goes through all cities and add up all the distances and there you go. This specific path is the certificate that gives us a positive answer. It is easy to see that the whole P class is contained in the NP class and the P vs. NP problem asks whether there are problems in NP that are not in P. In other words: is P strictly contained in NP or not?
Now, how can we visually represent this problem? My first two approaches were quite descriptive, like putting into images what I just explained with words. The first idea was a Joan Miró fashioned Venn diagram. Joan Miró was a Spanish artist from the past century who interpreted the world mostly in terms of black lines and circles and colorful intersections. Many landscapes of his seem familiar and strange at the same time, which is parallel to visualizing a well-studied but open mathematical problem. Different circles and shapes would represent the different classes. This would also fit another observation by Cook: there are far more classes in this theory besides the P and NP class. In fact, there are more than 50 different classes which mathematicians are currently working on and just like with the famous pair, there is still work to be done concerning the relationship between the different classes. However, this was precisely the problem with this first approach: if we do not know the relationship between the different classes, how can we represent the problem like a Venn diagram?
The second idea was, again, mostly descriptive, but referring to a different aspect of this theory. In fact, among the different classes, there is a particular one which is quite interesting to the P vs. NP conjecture. It is the NP-complete class. A problem is NP-complete if all other problems in NP can be reduced to it in polynomial time. The importance of this class is hidden behind the fact that if only one NP-complete problem is proved to be solvable in polynomial time, then immediately each problem in NP would have a polynomial time solution. In other words, this would prove that P=NP. So proving that just one such problem belongs to P, means that there would be no hard problems left. I picture a circular domino effect: no matter which piece falls, all other pieces would fall as well. So a circular domino sculpture would describe this fact very well. In addition to this, if the dominoes are glued to a platform, this would also make an further, hidden statement: it does not seem like the dominoes will fall at all. Cook himself joins the common scientific opinion, that P does not equal to NP. We will not find a loose domino.
However, as you may imagine, I was not satisfied with these two ideas. The reason for this is that they do not faithfully visualize what this problem represents for the mathematical community. What we feel when we think about it and what a solution to the conjecture would mean. If the known mathematics is a map, then conjectures like this one represent the limits of the known world. Something humankind wishes to know and understand better. We ignore what can be found behind these areas and the mere idea of facing them seems to be a perilous and foolish endeavor. And this is when I got another idea. The first world maps labeled unexplored territories with the inscription Hic sunt dracones – Here be dragons, together with the depiction of sea monsters and mythological creatures. Now, what is an open conjecture if not a mysterious, untamed monster waiting to be conquered? We might think that we understand it, but truth is that only the most skilled adventurers may have a serious chance against this beast. Here two observations by Cook come to my mind. The first is a personal anecdote he shared, telling me that he gets 1-2 emails per week from people claiming that they solved the problem (until now they appear to be unsuccessful). The second one is that he highlighted the great effort made by the most distinguished specialists in the area in order to solve the problem. In conclusion, it seems to be a hunt indeed. The glory that comes with a definitive answer to the P vs. NP issue is comparable to the glory of overcoming a beast in tall tales. So, behold the result of all these thoughts.
In classical medieval style, my monster is a mix of different real world animals. This can frequently be observed in tapestry all around Europe, where the artist creating the tapestry depicted strange and exotic landscapes without ever having visited them. Based on the description of the explorers, strange creatures emerged from this interaction. The inscription in Spanish, This monster cannot be tamed in polynomial time, is a reference to the problem I am depicting and follows Magritte’s style, which was the theme of the intercultural science-art project during the 7th HLF. Naturally, this is a very personal interpretation of the problem. I hope you find it interesting and imagine that if this experiment was repeated by anyone else, the result would be entirely different. This, however, is an encouraging thought.
I would like to thank Stephen Cook for the time he spent discussing the conjecture with me. Here I presented a visual representation of P vs. NP, which does not mean that it is the only way of explaining a mathematical idea to the world. In this context, I invite you to join this initiative by
1) thinking of a song you like that could also represent the P vs. NP conjecture
2) thinking of a person of human history of any area you like (not necessarily a scientist) who could have had what it takes to solve the problem (if the person was a mathematician).
Please share your thoughts in the comment section. I am looking forward to reading them!
Der Beitrag Explaining the P vs. NP conjecture – a different approach erschien zuerst auf Heidelberg Laureate Forum.