Written By Sneha Senthilkumar (Grade 11)
P versus NP is considered one of the most important unsolved problems according to many mathematicians and computer scientists.
But, before diving into the actual problem, you should know the context and history of this problem. Although traces of this problem were speculated openly through history, Stephen Cook, who was an American-Canadian computer scientist and mathematician, in his seminal paper, formally defined the problem in 1971.
Many consider P versus NP the most important problem in computer science. To make things more exciting, P versus NP is one of the seven Millennium Prize Problems selected by Clay Mathematics Institute and whoever provides the first correct solution to any of these problems, will get a cash prize of $1,000,000. But here’s the catch – these problems are extremely tough, near impossible, to solve and that’s stating it lightly. Only one problem, the Poincaré Conjecture, has been solved so far, whilst the remaining have remained unsolved, since the twenty years of their official announcement.
Now, let us take a look at what the P versus NP problem is all about.
P versus NP is an infamous unsolved problem in the field of mathematics and computer science, and to put it in a nutshell: Is it possible for every solved problem whose answer can be verified quickly by a computer, also be quickly be solved by a computer?
‘P’ refers to those problems that are fast (hence easy) for a computer to solve. ‘NP’ refers to those problems that are fast (hence easy) for a computer to check but not necessarily easy to solve in the first place. You will have to keep this in mind, so here is a shortcut to remember it – ‘P’ = fast to solve and ‘NP’ = fast to check.
Take prime numbers, for an instant. Prime numbers are numbers only divisible by themselves and 1. Now, it is easy to check whether a number is prime or not, but it is hard to find all those numbers in the first place.
So why should we care about this whole P versus NP problem? Well, this problem can be applied in our real world too. Let us imagine, that you are the head of security of a large museum. The national museum has over 40 rooms, and it holds many extremely rare and important artifacts. To ensure, that any thieves do not steal these artifacts, you are given orders to install cameras to keep an eye on every artifact. You want to know if 200 cameras are enough, such that each artifact can be seen by at least one camera.
So, let’s imagine, to satisfy this condition, we need 150 cameras. Now, since I have told you the answer, it is really easy for you to check if all these 150 cameras do, in fact, cover all the artifacts in the museum. However, if you did not know this answer, and you had to calculate it from the beginning yourself, it would surely take a lot of time. This is one of the simplest examples for the application of P versus NP problem in the real world
But here is the best part. Many such NP problems remain hard to be solved easily. But even if we find one solution or one easy method to use to solve even one NP problem, it can be applied to all NP problems, especially NP problems that computers cannot solve. It could be a definite game-changer in computer science and mathematics.
Now that you understand its significance, let us see the conclusion drawn by the science and mathematics community. The real questions is, are NP problems different from P problems, or are NP problems just the same as P problems? If the case is the latter (P=NP), then that could mean there are possible easier and faster problem-solving methods that do exist for problems that are difficult for computers to solve, and we just have not discovered them yet. However, if the case is the former (P≠NP), then no matter how hard we try, NP problems will forever remain to be too difficult to solve.
So far, there are no easy or fast solving methods for NP problems, which lead mathematicians and scientists to think there are NP problems other than P problems. However, there is no mathematical proof for it. Thus the search for solid evidence continues, as P versus NP remains one of the most mind-boggling and difficult problems to comprehend, let alone solve!
Featured Image Courtesy – Big Think