P vs NP — Smarter than Turing? Become a Millionaire !
Do you have any “Problem”?
We live in a world of chaos. We solve problems on daily basis, some are trivial and some are complex. It’s in our nature to solve the problems, to find out the solution, and not just solution, we always tend to find out optimized solution.
For example, let’s say you are getting late and you want to reach office on time (yeah.. once upon a time — a pre March 2020 era). You know that your usual route to office might be congested due to peak traffic hours, so you would decide to take some alternate route. You would calculate and decide an alternate route in your mind based on some factors like alternate route might be a short cut, or an express highway where you can drive fast, or its relatively less known to public, or would metro make you reach faster than your own car, or less number of traffic signals. Let’s say, after some consideration you have concluded that out of route A, B, C and D, route A and route D would be the best. You start driving on route A, but there is a huge traffic jam due an unfortunate accident. Now you are cursing yourself, that you should have taken route D, probably that's the best route.
Now, the real question would be, are you 100% sure with absolute certainty that route D is the best route? May be route C is the best route, which you totally ignored. The important point here is that you cannot know with 100% absolute certainty that which route is best unless you take all routes. Apparently you have better things to do at office rather than taking each route one by one and determine which is best.
Even if you want to take all the routes and see which is best, you cannot take all routes simultaneously at the same time. So, you would have to take each route one by one. Even then you cannot say with 100% absolute certainty which route is best, because since you have taken the alternate routes one by one, the time window is different. May be route B gets congested at 1 pm due to school buses leaving from the schools on route B, or when you cross route C at 2 pm, may be it was closed and you are forced to take a diversion due to a fallen electric pole.
You cannot determine the optimal solution of this problem, unless you travel on all the routes simultaneously at the same time, which is physically impossible. The take home point from last 3–4 paragraphs is only one — i.e. you can determine the solution of this problem in exponential time, but not in polynomial time or in other words, non exponential time.
Unless you have a Nondeterministic Turing Machine (NTM), which can solve this problem by taking all routes at once, you cannot have solution in non exponential time. Unfortunately NTM are theoretical and do not exist. You, me and all our computers are just humble normal plain vanilla boring Turing Machines.
Polynomial and Exponential — Alien words?
If you are reading this far, then surely you would like to know and understand more about all this brouhaha about polynomial or exponential or deterministic or non deterministic or Turing machine.
So, let’s try to understand these terms.
Have you played any game of playing cards? One player shuffles and distributes the cards randomly. Then, you pick up each card one by one and arrange the cards in your hand.
If you have ever arranged the cards in your hand, then knowingly or unknowingly you have performed “Insertion Sort”. Insertion Sort is an algorithm or set of steps, which can be followed to sort any thing. Considering, each hand consists of 13 cards, so to sort these 13 cards, you have performed 169 steps. Whow… That’s lots of steps. How can I tell this number with surety? Let’s calculate. You have 13 cards upside down. You take each card and put in your hand. For every card you take, you scan each card in your hand. So, for 13 cards, you are scanning all cards in your hand 13 times. That’s the number — 13 x 13 = 169
In this case the input size was 13. What if you have to sort 15 cards? It will be 15 x 15 steps. So, wouldn’t it be better to say that if you have ’n’ cards, then you would be performing n x n steps or in other words n^2 steps. This calculation of number of steps based on input size is called as Time Complexity.
Another example, let’s say your friend gave you his locker key, and asked you to go and take out his belongings from the locker. So, you go to locker room, and you see there are 100 lockers in the room. You don’t know in which locker the key will fit. So, you would start trying to open each and every locker from 1 to 100. So, maximum you will take 100 steps. If there are 500 lockers, you will take 500 steps. If there are ’n’ lockers, then you will take n steps.
So, you must have realized by now that each solution can be divided in steps, and number of steps is dependent on input size. For some algorithms the complexity is ’n’, for some other algorithms it can be n^2,, or it can be n^3, or it can be logn or n log n etc. All these complexities can be termed as “Polynomial”.
Now, it’s safe to say that there are many problems which has polynomial solutions, like sorting, or searching, or multiplying, or finding permutations & combinations, or any other problem which can be solved by any human or any modern computer. These are also deterministic solutions. Deterministic means that for any particular given input, the output produced will be same. For example, if I ask you to tell me the minimum integer value from the series 4, 2, 7, 1, 9, 3, 5, then the answer will be always 1, even if you run the same program trillions of times. Input and output are tightly coupled.
On the other hand, we have algorithms or solutions to the problems, which may give different outputs for same input. For example, a concurrent program may perform differently due to race conditions, or probabilistic algorithm may behave differently and produce different output based on random number generator. For example, if you and me would engage in a game of Chess. In some games I may win, in some games you may win, and some games may end up as draw. Input is same, that is you, me and chess, but output is different at the end of each game.
A deterministic or brute force algorithm might take eternity to determine who would win the game, because there are so many possibilities a player can move the Chess pieces. At each step, the move can be any of 16 pieces from one player. If a modern computer would try determining the winner by considering each and every possible movement, then the computer will take more than the age of universe to compute the result. Certainly we won’t be alive for billions of years to see the result of a chess game by deterministic computer if it would be still running.
These certain set of solutions to problems which take exponential time are having exponential time complexity which can be represented as 2^n or 3^n or worst n^n.
To put things in perspective, if input size n is 100, and if the algorithm’s complexity is n3 then it would take may be a couple of hours to solve the problem. But, if we have an exponential algorithm, then on same input size if the time complexity of an exponential algorithm is 2^n then the problem will get solved in quintillion years, i.e. 1 with 18 zeroes. That’s more than many trillion times the age of universe.
These exponential solutions have one good property. These solutions run in exponential time, but to verify whether the output is correct or not, it takes polynomial time. Example, running a chess game might take billions of years, but at the end if we want to verify whether player A won or player B, then we can instantly tell it.
Another example — Sudoku puzzle, solving a sudoku puzzle is an exponential solution, but once solved, its very easy to verify whether the solution is right or wrong in polynomial time or instantly.
The set of problems which have a Polynomial solutions are called as P Problems.
The set of problems which have an exponential solution, but can be verified easily in polynomial time are called as NP Problems. These are called as NP problems, because a Non-deterministic Turing machine (which is theoretical) can solve this exact same exponential problems in polynomial time. Thus named as Nondeterministic Polynomial or NP Problems.
Examples of NP problems — Chess, Sudoku, Go game, Tetris, Candy Crush, Traveling salesman, finding best route, Protein folding (Lavinthal Paradox), weather patterns, brute force decryption, circuit design etc.
Bigger Questions
Whatever we have discussed till now, it is the basics of Computational Complexity Theory. Computational complexity is in itself a big subject and an area of intense research. But why all this really matter or important at all? We understand that some are P class problems and some are NP class problems, so what’s the big deal in it. We have classification of so many other things, then why does the classification of problems should be treated differently? How it will make your life better? Why this P vs NP should be discussed? Why P vs NP is the biggest unsolved mystery in the world of computer science? Who would give a million dollar for such a trivial thing where you are just looking at classification of problems?
The horizon is much much bigger than whatever I can write here. But I will try to answer all this bigger question, and make sure that you will understand that why this P vs NP is such a big deal, atleast as big as 1 million dollars in prize.
Bring me that Horizon
As we have seen till now, we have two classification of problems, one is P and the other is NP.
All the P problems can also be solved in exponential time. So if we look closely, all the P problems are also NP problems, but not all NP problems are P problems. Its like saying, all chickens are birds, but not all birds are chickens. P is just a subset of NP.
So, now we know that some NP problems can be classified as P problems, but the bigger question is, can we classify all NP problems as P problems?
My life is unaltered, I don’t care !
If you are really thinking that whats the point of all this nonsense, It’s not impacting your life. Certainly you won’t suddenly become Superman by knowing all this Polynomial or Non Deterministic bla bla.
Hold that thought for a moment.
If you can prove that all NP problems can be solved in Polynomial time, or any problem which can be verified in Polynomial time can also be solved in Polynomial time, then you are essentially proving that all NP problems are actually P problems, or in other words P will become equal to NP. P won’t remain just a subset of NP problems, but P will become the one and only set of problems.
If P is proven to be equal to NP, then it essentially means that there exist an algorithm which can solve the problem in few minutes or few hours rather than taking billions of years.
It would mean that, there exist a solution for the most efficient routing. It can improve the logistics of global civilization beyond our imagination.
It would mean that, there exist a solution to protein folding, which would essentially break the Lavinthal Paradox, and new drugs can be made in matter of few days rather than decades. It would mean that you can cure cancer by the time you celebrate your next birthday.
It would mean that, we can predict all the tsunamis, hurricanes, earthquakes months in advance with absolute certainty and save millions of people each year.
It would mean that you can claim your 1 million dollar from Clay Mathematics Institute which has put the prize for anyone who can prove P = NP.
It would mean that all the encryption can be broken very quickly, and the cybersecurity will become a myth. Good luck saving your newly earned 1 million dollars in your bank account.
It would simply mean that the world will change. All problems which were deemed unsolvable, will become solvable. The progress of human civilization will become exponential, by pulling the exponential problems under the ubrella of polynomial problems. That is why P = NP is such a big deal.
How can I prove P = NP?
Let’s play a game. Let’s say we have numbers from 1–9. We can choose one number at a time. We take our turns alternatively. The player whose number will add up as 15 first, will be the winner.
1 2 3 4 5 6 7 8 9
Suppose
- I pick 9
- You pick 6
- I pick 4
- You pick 8
- I pick 2. Now at this point my sum of numbers is 15, so I win.
Does it look any familiar? No…. Let’s rearrange the problem.
Now, if we play the same game after rearranging, it will be exactly similar to playing Tic Tac Toe.
That essentially means that we have reduced our problem into a more common problem. Any algorithm which can be used to play tic tac toe, the same algorithm can also be used to play magic square of any number, not just 1- 9 & 15. Vice versa, any algorithm which can be used to play magic square, the same algorithm can also be used to play tic tac toe. If two problems can be reduced to same problem, then those can be solved by same algorithm.
We already know that some of the NP problems are P problems, because P is subset of NP. So, in order to prove that all NP problems are actually P problems, you have to find a polynomial solution for atleast one of the NP complete (NPC) problem, or reduce one of the NPC problem to some problem which is known to have a Polynomial solution. The NP complete problems are those problems for which no known polynomial solution exist.
Many believe that P is not NP. Of-course it hasn’t been proven till now that P is equal to NP, or P cannot be equal to NP. There are so many other things which are not proven till now, for instance, no one has proven that ghosts or supernatural powers are real.
On a separate note, there is a one million dollar prize to prove supernatural phenomena too — https://en.wikipedia.org/wiki/One_Million_Dollar_Paranormal_Challenge
Why reduce problem? Why not invent NTM?
The debate is on. The NTM is purely theoretical and an ideal computer. The closest we can get to an NTM is a Quantum Computer. Because even quantum computers are subject to quantum errors and quantum fluctuations. A quantum computer works on superposition and probabilities. There are problems in NP that we don’t think can be solved in polynomial time on a quantum computer, where as a non-deterministic Turing machine can indeed solve NP-complete problems in polynomial time. An NTM is theoretically vastly more powerful than a quantum computer.
There are some problems for which a polynomial quantum algorithm exists, and those problems can be solved by quantum computers in polynomial time, example Integer Factorization problem. There is no polynomial solution for integer factorization, but there exist a quantum algorithm which can solve integer factorization in polynomial time in quantum computers. Such problems are classified as BQP or Bounded-error Quantum Polynomial time problems.
There are some evidences (https://www.scottaaronson.com/papers/bqpph.pdf) that show that the BQP problems are outside P-NP space. If BQP would really be outside of P-NP space then it would essentially mean that even if P = NP, but BQP != P or NP.
So, if you solve the P vs NP, then a new battle would start which would be called as P vs BQP.
Currently we really don’t know if BQP is outside of P-NP space, or inside the P-NP space. Looks like in problem space also the quantum behavior is fuzzy, and in superposition, i.e. inside and outside of the P-NP space at the same time.
Cliffhanger
There is another set of problems called as NP Hard, for example Halting Problem. Some NP-Hard are NP Complete, but majority of NP Hard problem lies totally outside of P-NP space. The NP-Hard problems like Halting problem would require a different article in itself to understand it much better.
At the end …
Instead of providing a summary of everything mentioned or discussed here, I would like to end this article with a quote by a one of the renowned Computational Complexity Theory pioneer, Scott Aaronson.
“““
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.
- Scott Aaronson
”””
On a separate note, if this article has inspired you to find out the solution of P vs NP problem, and change the world, and you go on to win the 1 million dollar prize, then don’t forget my share in that prize money.
