In physics we have the idea of extensive and intensive properties. An extensive property. such as volume, is one that depends on the whole system. An intensive property, such as temperature, is one that depends on just a part of the system. In the same sort of way you can think of the property of being divisible as an extensive property that demands a search for a divisor whereas being prime is an intensive property that depends on something inherent in the number and needs no search.
So what does this mean for P=NP?
As prime testing is in NP, surely finding a polynomial solution means that it is in P, and hence NP=P. Not so, because prime testing is not NP complete. An NP complete problem is one that typifies the entire set of NP problems and a polynomial solution to an NP complete problem would provide a polynomial solution to all NP problems. If this were the case then indeed P=NP.
The travelling saleman problem is NP complete and proving that there is a solution in P would also prove that P=NP. When you think about the task it seems very unlikely that there is a solution to the travelling salesman problem that doesn't involve a complete search. To prove that this is the case you would need to find an intrinsic property that indicates the size of the smallest tour to avoid the need for a search.
No comments:
Post a Comment