The One Million Dollar Question

There are many exciting questions that anyone can spend a part of his life, if not his whole life, trying to solve. Their prizes are quite attractive. Their complexity is not. Solving some of them equals one million dollar each. In mathematics, the list of unsolved problems, called the millennium prize problems, includes P versus NP, Hodge conjecture, Riemann hypothesis, Yang–Mills existence and mass gap, Navier–Stokes existence and smoothness, and Birch and Swinnerton-Dyer conjecture.

In this article, I want to review the excitement of the first one, i.e. P versus NP problem, which I witness everyday implicitly throughout my research. I especially seek to highlight what does solving this question mean from a practical perspective.

History

Considered to be the most important active problem in computer science, the “P vs NP problem” was first presented, despite being present implicitly, in a paper entitled “The complexity of theorem proving procedures” by the Professor Stephen Cook in 1971. Before this official date, many problem instances were noticed. Among them was the remark shared by another mathematician, John Nash highlighted in a letter written to the national security agency (NSA) that the time necessary to crack a quite difficult code is exponentially linked to the length of the key. Proving this speculation is equivalent to P ≠ NP. The reason lies in the possibility of checking any given key in polynomial time.

Mathematical Lexicon

The problem has been present for 50 years so far. To ensure its understanding, one might need a quick overview of the lexicon. The first term or class is P, which contains all the problems that be solved in polynomial time in the size of the input. For instance, if the input size is N, then the resolution time should be in the form N, N², etc. For example, all the conventional arithmetic operations such addition, subtraction, multiplication, division, and comparison can be done in polynomial time. The second term or class is NP, which contains all the problems for which the solutions can be checked in polynomial time given the right information. Obviously, from the definitions, P ⊆ NP. Still, the inclusion does not mean equality. With these two classes, another class emerges, which is NP-completeness. This class contains a set of problems, which any other NP can be reduced in polynomial time while maintaining the possibility of verifying the solution in polynomial time. Then, an NP-complete problem is an NP problem at least as difficult as any other problem in NP. Finally, we have the NP-hard class. It contains all the problems at least as hard as NP problems.

Consequently, if any NP-complete is in P as well, we will definitely have P = NP. Unfortunately, several NP-complete are known but no rapid algorithm is available to solve them.

Geometric Interpretation

Based on the lexicon presented above, we have two possible situation as presented below. In the case where P ≠ NP, the classes remain diverse. In the case where P=NP, we end up with two main classes P and NP-hard. In the left figure, one can easily identify problems in NP, which we are not sure whether they are in P or NP-complete.

Problems in NP not known to be in P or NP-complete, also referred as NP-intermediate.

Problem Reformulation

Looking to the problem from a pure mathematical perspective may seem very complicated. The easiest game used to highlight the problem is the Sudoku. In this game, each line, column, box should have, without repetition, numbers from 1 to 9. As the grid size gets bigger, the problem becomes more complex, and resolution time grows exponentially. Still, it is very easy to check whether a given solution is correct or not. Hence, the Sudoku is rapidly checkable, i.e. NP, but there no algorithm has been found yet that can solve a grid in polynomial time. Scientists has been taking many years to deal with games like Sudoku and others. Research has not lead to any fast resolution techniques. However, this keeps the question open and cannot lead to any conclusions. If one can prove, for a game like Sudoku, that it can be solved in a polynomial time, she/he will prove that NP=P.

What has been explained for Sudoku is valid for Chess, Go, and other games. The question can then be formulated as follows: Does being able to quickly recognize correct answers mean there is also a quickly way to find them?

Problem Significance

To highlight the significance of the problem and its resolution, I would like to highlight the quote of the theoretical computer scientist Scott Aaronson. These few sentences a quite deep and by just reading them, one can feel how many doors might be opened if P=NP.

“If P=NP, then the world would be a profoundly different place than we usually assume to be. There would be no special value in ‘creative leaps’, no fundamental gap between solving a problem and recognizing the solution once it is found. Everyone who could appreciate a symphony would be Mozart, everyone who could follow a step-by-step argument would be Gauss.” — Scott Aaronson.

In such a case, the discovery of any mathematical proof can be fully automated. There have been many attempts to solve the problem, some tried that the problem is unprovable, some others tried to prove either that P ≠ NP or P ≠ NP. So far, the question is still open and no proof is available. The problem may be unsolvable. Yet, the upcoming years, decades, centuries may bring some new exciting insights !

What are your insights on the topic? I am looking forward to hearing them :-).