And why solve one of them can solve all,how does it be proved
In: Mathematics
I’m not sure what the question in your title means, but I’ll answer the second one.
So, we’re looking at two categories of problems – P and NP. Without getting into much details, P problems are problems that can be solved quickly (i.e. you can write a relatively efficient computer program that finds a solution). NP problems are problems that, given a proposed solution, we can check quickly whether this solution is correct.
Now, lets say we have two problems, lets call them A and B. If we can write an efficient program that will translate an input to problem A to an input to problem B and then translate the solution of problem B to a solution of problem A, we say that problem A can be *reduced* to problem B. This basically means that if we found a solution to B, it also serves as a solution to A.
A problem is called “NP-complete” if every problem in NP can be reduced to it. Suppose we have some problem in NP-Complete (let’s call it L). If we want to solve some other problem in NP, we can just reduce the problem to L and then solve L. If we manage to find an L that can be solved easily, then it means that we can easily solve any problem in NP. If L happens to be in P, then it means that every problem in NP is also in P, which means P=NP.
Latest Answers