Gerrad Hardy P vs NP

P vs NP

Figure 1: P ≠ NP. Reprinted from flikr.com, by J. Kaláb, 2010,
Retrieved from https://www.flickr.com/photos/pitel/4900893832/in/photolist-8t5mZw-6hHhF4-czRVuY-ejA75v-dgzQkv/. Copyright [2010] by Jan Kaláb

               P vs NP is one of the seven millennium problems posed by the Clay Mathematics Institute in 2000. The article I am reviewing is the definition of this problem written by the first man to precisely define the problem, Stephen Cook. The article is broken into three parts: the first being about the problem and very clearly defining it using a combination of math and logic statements, the second focusing on the history and importance of the problem, and finally the third being about different conjectures (a conclusion based off of incomplete information) and failed attempts to prove it. In this post, I aim to help you understand the problem without diving into the math/logic used in the formal definition, and then to share with you the importance of this problem and why it was chosen to be one of the seven millennium problems.

               Before diving into the definition some things need to be explained to prepare you to be able to understand the problem and its importance. Those things are what exactly is a millennium problem and time complexity which is the idea the problem is centered on. As mentioned above this P vs NP problem is one of the seven millennium problems proposed by the Clay Mathematics Institute on May 24^th, 2000. These seven problems were some of the most difficult and important problems at the turn of the century and as such the Clay Mathematics Institute put out an offer of one million dollars to anyone who could solve one of them. As of today, 19 years later, only one of the seven has been solved (The Poincaré Conjecture). These problems are very difficult to even understand, as their definitions require a lot of specialized and advance knowledge in their respective fields. NP vs P, however, is considered one of the easiest to understand as it is easy to relate to common problems and task.

               While I could just use real-world examples to explain P vs NP, my explanation will be lacking without an understanding of time complexity, the central idea the problem is based off. Time complexity in computer science describes the amount of time it takes to run an algorithm. An algorithm is defined as a process or set of rules to be followed in calculations or other problem-solving operations. As the problem grows so does the complexity but essentially time complexity is how long a computer will take to solve a problem following the direction of a given algorithm. Time complexity can be measured in multiple ways, but the way computer scientist tends to care most about is the worst-case time complexity. So, if I ask a computer to do something like add a list of numbers together what is the worst-case scenario? What is the longest it would take to solve that problem? Problems can be mapped by specific function types like a polynomial or exponential function but what is important to understand is time complexity is essentially how long a problem will take to solve as it gets bigger and more intensive.

                Now that we have that all out of the way I can move onto the problem of P vs NP. Problems can be split into different levels of complexity. As you go up in levels the problems take longer and get harder to solve by computers until you have problems that can never be solved no matter how much time or what computer is used (i.e. the halting problem). P problems are problems that are easy to find a solution and check that it is right. NP problems are a level above P problems where the solution to a problem is hard to find an answer but if an answer is provided you could go and check if it was correct. P problems are easier problems for computers to solve and as the values used increases it stays pretty simple for a computer to solve. NP problems, however, are not easy to solve in the sense that as the values used in the problem increases, things quickly begin to get out of hand and require large amounts of time in order for the computer to solve. This goes back to how complexity can be mapped by a function if you want to dive more in depth about the differences but for now, I will leave it at that.

When I first had that explained to me, I still found it hard to follow. It wasn’t until I had these ideas explained to me using real-world examples that it really started to connect. Some examples of a P problem would be addition, multiplication, or solving a Rubik’s cube. Focusing in on that last one because everyone knows how difficult a Rubik’s cube can be and it is easy to visualize. Well, there are a set of rules you can use to solve which results in a completed Rubik’s cube no matter the orientation. For a human doing this on a 3x3x3 cube can take a while but for a computer following these steps are just simple calculations. Let scale up the Rubik’s cube to say 100x100x100 now. To a human that would seem impossible, but for our computer following a set of rules (the algorithm) it doesn’t really matter what size the cube is. Modern computers can handle and work with enormous numbers and the act of running computations using those number just doesn’t get harder faster than the rate that computers performance has been increasing.

NP does get harder fast. As the numbers used in NP get larger so does the difficulty and time needed by computers to solve these problems. Sticking with the well-known puzzle theme, Sudoku is an example of an NP problem. If you ask a computer to solve a classic 9x9 sudoku grid it could do it quick enough that you may not think it was difficult but what if we made it bigger? What if we asked it to complete a 100x100 sudoku grid? As the grid grows the difficulty of the problem grows out of hand very quickly even for the strongest computers. This is because the rules the computer uses to solve sudoku are not as efficient as the one used on the Rubik’s cube; the algorithm is more complex. If I gave the computer a solution to the 100x100 grid however it would be able to tell quickly if it was correct or not. This is the problem with NP is there just isn’t a quick, efficient means of solving the problems.

The problem asked by Stephen Cook in his P vs NP paper is does P = NP or does P ≠ NP? What this means is are all NP problems just P problems that we haven’t figured out the best way to solve them or are there just some problems that will always be NP. Whether P or NP is determined using the function that maps the complexity but in essence, it is saying that these really difficult problems may actually not be so difficult, we just haven’t figured out how or there really is no easy way to solve them. Most computer scientists believe P ≠ NP simply because of the consequences of P = NP.

Figure 2: P = NP taken  Reprinted from flikr.com, by L. Domnitser, 2009, 
Retrieved from https://www.flickr.com/photos/ldrhcp/3470903457/in/photolist-8t5mZw-6hHhF4-czRVuY-ejA75v-dgzQkv/. Copyright [2009] by Leonid Domnitser

So, why is this important whether a computer takes longer on some problems than others? Why was this posed as one of the biggest problems of the century? Well, that is because some of the problems in NP have world changing effects if they were easier to solve. One example is protein folding which is the process in which protein chains assume their three-dimensional shapes allowing them to complete their task. If we can understand and replicate protein folding easily humans could use it to combat or cure cancer and any other disease. Another example of an NP problem that world-changing results are public encryption keys used by banks, governments, or any other group that wants to keep information private. These encryption keys are based off NP problems so if there is an easy way to solve NP problems then figuring out the key wouldn’t be difficult. Our whole online security system would become insecure.

If P=NP, the world would have miracle answers to a lot of pressing issues almost overnight. If P≠NP, then that knowledge would spur computer scientist to overcome the complexity gap in other innovative ways such as machines able to handle NP problems efficiently. Either way, a proof of either would have a huge impact on computer science and would catapult the author of said proof into international fame in the academic world.

References:

Cook, S. (2000, May 24). THE P VERSUS NP PROBLEM [PDF]. Peterborough,NH: Clay                                 Mathematics Institute.
Domnitser, L.  (2009).Strange Graffiti at the Engineering Building [Online image]. 
             Retrieved April 14, 2019 from 
             https://www.flickr.com/photos/ldrhcp/3470903457/in/photolist-8t5mZw-6hHhF4-                                 czRVuY-ejA75v-dgzQkv/
Kaláb, J.  (2010). P != NP [Online image]. 
             Retrieved April 14, 2019 from
             https://www.flickr.com/photos/pitel/4900893832/in/photolist-8t5mZw-6hHhF4-                                   czRVuY-ejA75v-dgzQkv/