Before getting to the million dollar question of this millennium (Seriously, Clay Mathematics Institute is offering $1 million to whoever solves it ), lets make ourselves familiar with the fancy terms P, NP, NP-Hard, NP-Complete.
First, let's understand what NP is.
Suppose you stumble upon a Sudoku puzzle that you just can't seem to solve. Then, a friend walks up to you and boasts, "Haha! I know the answer to the problem!" Amazed, you tell your friend, "Prove it!" Your friend fills out the empty spaces in your Sudoku puzzle, and behold, upon a quick glance, you've verified that the answer is correct. "How did you do that?" you asked your friend. He responds, "It doesn't matter ;)"
Sudoku is an NP problem because it you can "quickly" verify a solution to a Sudoku problem. (By "quickly", I really mean "in polynomial time.") It doesn't matter if you can actually figure out the solution quickly or not. All that matters for a problem to be in NP is if a solution can be verified quickly.
Now keep this little story in mind while reading these definitions :
Consider linear search problem (searching a number in a list of numbers). You can find this number in linear time or O(n). Or consider binary search, that takes O(logn) time or a problem that can be solved in quadratic time O(n^2) time.
All these problems have one thing in common, they can be "SOLVED" in polynomial time.
if the algorithm runs in linear time or quadratic time or cubic time, then we say the algorithm runs in polynomial time and the problem it solves is in class P.
So in the story above, SOLVEing a problem may not have taken polynomial time, who knows what algorithm he used to solve the Sudoku. However, to "VERIFY" that he solved the Sudoku correctly, we can do that in polynomial time!
This means there is not necessarily a polynomial-time way to find a solution, but once you have a solution it only takes polynomial time to verify that it is correct. So if the solution to a problem can be checked in polynomial time, it is called NP problem.
NP is called "Non deterministic" because of Turning Machine. So this guy, Turing, invented a machine that can solve decision problems. In other words, if you feed the machine the problem and the solution, it can tell in polynomial time if the solution is correct or not (YES/NO).
P.S. :
I used to confuse it with Non Polynomial Time ( which would mean it can't be solved in polynomial time), a big blunder!
These are the rouge problems, like James Bond who dont like to play by the rules. NP-Hard problems need not be NP i.e. some problems that cant be even verified in polynomial time, they may or may not take PTIME to verify the solution. Unlike P and NP that are decision problems, NP Hard can be Decision, Search or Optimisation problems. These are called "Hard" because they are almost as hard as NP Complete problems. ( discussed next ).
-> NP
-> NP-Hard
As we know NP-Hard may or may not take PTIME to verify, those NP-Hard who takes PTIME are called NP-Complete.
It has been proven that any NP-Complete problem can be converted to any other in PTIME using many-one reduction techniques!!! This leads to a very interesting theory...
Solve one, just one, any one! problem in PTIME, and rest can be solved automatically in PTIME. Sounds like magic, doesn't it? :D
Science behind the magic : Since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.
This leads to the ultimate debate, if NP problems could be solved in PTIME, is it true that...
P = NP ?
Its clear that P is a subset of NP. The think that isn't clear is if NP can be solve d in PTIME. cause if they can be, P would indeed be equal to NP.
Travelling Salesman Problem (TSP) is a very famous real world problems that questions simply, If there are n cities connected to each other, let there be a salesman in city 1. Given the time between each pair of cities, Whats the minimum time such that he visits each city exactly once returns back to 1?
No efficient solution to this, but approximate optimal solutions are there.
TSP is a NP-complete problem because of two properties :
1. No efficient solution in PTIME exists, but can be verified in PTIME.
2. Every instance of hamiltonian path is reducible to a TSP problem and it has been proven that Hamiltonian path problem is NP complete, TSP is NP complete.
1. Stackoverflow
2. Quora
First, let's understand what NP is.
Suppose you stumble upon a Sudoku puzzle that you just can't seem to solve. Then, a friend walks up to you and boasts, "Haha! I know the answer to the problem!" Amazed, you tell your friend, "Prove it!" Your friend fills out the empty spaces in your Sudoku puzzle, and behold, upon a quick glance, you've verified that the answer is correct. "How did you do that?" you asked your friend. He responds, "It doesn't matter ;)"
Sudoku is an NP problem because it you can "quickly" verify a solution to a Sudoku problem. (By "quickly", I really mean "in polynomial time.") It doesn't matter if you can actually figure out the solution quickly or not. All that matters for a problem to be in NP is if a solution can be verified quickly.
Now keep this little story in mind while reading these definitions :
P (Polynomial Time Running )
Consider linear search problem (searching a number in a list of numbers). You can find this number in linear time or O(n). Or consider binary search, that takes O(logn) time or a problem that can be solved in quadratic time O(n^2) time.
All these problems have one thing in common, they can be "SOLVED" in polynomial time.
if the algorithm runs in linear time or quadratic time or cubic time, then we say the algorithm runs in polynomial time and the problem it solves is in class P.
NP ( Non deterministic Polynomial Time)
So in the story above, SOLVEing a problem may not have taken polynomial time, who knows what algorithm he used to solve the Sudoku. However, to "VERIFY" that he solved the Sudoku correctly, we can do that in polynomial time!
This means there is not necessarily a polynomial-time way to find a solution, but once you have a solution it only takes polynomial time to verify that it is correct. So if the solution to a problem can be checked in polynomial time, it is called NP problem.
NP is called "Non deterministic" because of Turning Machine. So this guy, Turing, invented a machine that can solve decision problems. In other words, if you feed the machine the problem and the solution, it can tell in polynomial time if the solution is correct or not (YES/NO).
P.S. :
I used to confuse it with Non Polynomial Time ( which would mean it can't be solved in polynomial time), a big blunder!
NP-HARD
These are the rouge problems, like James Bond who dont like to play by the rules. NP-Hard problems need not be NP i.e. some problems that cant be even verified in polynomial time, they may or may not take PTIME to verify the solution. Unlike P and NP that are decision problems, NP Hard can be Decision, Search or Optimisation problems. These are called "Hard" because they are almost as hard as NP Complete problems. ( discussed next ).
NP Complete
-> NP
-> NP-Hard
As we know NP-Hard may or may not take PTIME to verify, those NP-Hard who takes PTIME are called NP-Complete.
It has been proven that any NP-Complete problem can be converted to any other in PTIME using many-one reduction techniques!!! This leads to a very interesting theory...
___________________________________________
| Problem Type | Verifiable in P time | Solvable in P time |
____________________________________________
| Problem Type | Verifiable in P time | Solvable in P time |
____________________________________________
| P | Yes | Yes |
| NP | Yes | Yes or No * |
| NP-Complete | Yes | Unknown |
| NP-Hard | Yes or No ** | Unknown *** |
____________________________________________
| NP-Complete | Yes | Unknown |
| NP-Hard | Yes or No ** | Unknown *** |
____________________________________________
" ONE PROBLEM TO RULE THEM ALL ! "
Solve one, just one, any one! problem in PTIME, and rest can be solved automatically in PTIME. Sounds like magic, doesn't it? :D
Science behind the magic : Since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time, all NP-complete problems can be reduced to any NP-hard problem in polynomial time. Then, if there is a solution to one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial time.
This leads to the ultimate debate, if NP problems could be solved in PTIME, is it true that...
P = NP ?
Its clear that P is a subset of NP. The think that isn't clear is if NP can be solve d in PTIME. cause if they can be, P would indeed be equal to NP.
Examples :
Travelling Salesman Problem (TSP) is a very famous real world problems that questions simply, If there are n cities connected to each other, let there be a salesman in city 1. Given the time between each pair of cities, Whats the minimum time such that he visits each city exactly once returns back to 1?
No efficient solution to this, but approximate optimal solutions are there.
TSP is a NP-complete problem because of two properties :
1. No efficient solution in PTIME exists, but can be verified in PTIME.
2. Every instance of hamiltonian path is reducible to a TSP problem and it has been proven that Hamiltonian path problem is NP complete, TSP is NP complete.
References :
1. Stackoverflow
2. Quora
No comments:
Post a Comment