You Win $1,000,000 USD For Solving this Computer Science Problem
P vs NP, one of the most complicated problems in theoretical computer science
This is possibly the greatest unsolved problem in computer science. Over time, it has percolated its way toward the field of Mathematics as well. Clay institute has set up a fund for solving different problems in Mathematics and they have announced a prize of million dollars for the person who solves the P vs. NP problem. It is the youngest of Millennium prize problems. In 1971, in his seminal paper, this bizarre problem was first and formally introduced by Stephen Cook. The paper was titled, ‘The complexity of theorem proving procedures.’ Its traces though are found all over history prior to 1971.
P vs. NP problem basically concerns the problems we want to solve on a computer. Certain kinds of problems are solved quickly by a computer while there are some, even for an advanced computer seems to take a long period of time. How come? It is because the problems that take a long time to solve involve a computer going to a vast number of possible outcomes to arrive at the right one. It begs the ultimate question of
‘If the problem is easy to check the solution to, is it also easy to find the solution to?’
During the early stage of program development for a computer, there was a race between the programmers to find the quickest algorithm to solve any particular problem. Problems like multiplication sorting found their way to be solved quickly while others like playing absolutely perfect chess, no matter how hard they tried, couldn’t come up with fast programs. This is where the actual problem comes in.
All the problems that could be solved by a reasonably fast program come under class P. And around class P, we discovered NP where if we’re given a correct solution to that problem we could at least check our solution in a reasonable amount of time.
NP problems included Vehicle routing(TSP), circuit design (SAT), and finding primes.
As time passed, some of the problems in NP turned out to be included in P where the exact solution could be solved using a fast-paced program, but for other NP problems, there still was a struggle to find a program that could solve them quickly. But then the programmers speculated a question
“Just because we couldn’t find a fast program to solve the NP problems, does it mean there doesn’t exist any? Will all the NP problems eventually turn out to be P, or are there some problems that are bound to be NP?”
That’s the P vs. NP question.
These problems are not just limited to the field of computer science and math. Any problems we encounter in daily life could be associated with P vs. NP. In the field of Biology, the question of a cure for cancer is, is always going to be incurable (NP), or are we eventually going to find a cure (P)?
A brief idea of what NP is could be drawn with the analogy to the problem of Sudoku. Finding out the right numbers to put on the box might take a long period of time, but if someone gives you the answer with filled-in boxes, it would be easy and will take a sufficiently small amount of time to check the mistakes. Outside the class NP, where problems are harder even to check, say what’s the best move to make in a chess game? Someone could tell you to make a certain move but how would you know that the person is right? To test this argument, we would have to build a complex program that is believed to be impossible to do so. On the other side, there are reasonable solvable problems of P. But these problems also fall under NP because one way of checking the answer to the problem of P is to find the answer yourself.
The amazing thing about this whole complex issue is the idea of what could be computed in a certain space and time. Rather than confining it to the nature of computation, we’re rather looking at the nature of space and time itself through this problem. This problem has its applications in the field of physics, biology, and ultimately our basic understanding of everything. Scott Aaronson, an American computer scientist, shared his intuition which gives the best outlook on how to perceive this problem when he said
“If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.”
Contributed by Rishab Karki and curated by the author.
Thank you so much for reading. If you liked this story don’t forget to press that clap icon. If you like my works and want to support me then you can become a medium member by using this link or buy me a coffee ☕️. Keep following for more such stories.
