Saturday, December 15, 2007

NP and Weirdness!

I just feel very weird about this whole NP class of problem. They are so many problems belonging to this class of NP and yet there are all the same. I can take one NP complete problem and can reduce that problem to another NP Complete problem in polynomial time. To quote that in plain words, If I have the algorithm to solve one problem, I can use that algorithm to solve the other NP problems. I just have to convert one NP problem to other in polynomial time! Even more weird is this thing: There is no known best solution for this problem. And to make things even more weirder, though there is no known best algorithm to solve this problem, but given a solution we can verify its correctness in polynomial time. That is, If you give me a solution to this problem, I can verify if the solution given is really a solution to this problem. That too, I can do this verification in polynomial time.

These are not the only weird things about NP class of problems. There are lot more. There is no known proof which either proves or disproves NP is equal to P or NP is not equal to P. But still any computer engineer will say that NP is not equal to P. If you ask the reason, then he will say if NP is equal to P then there should be a way to solve the NP problems in the order of polynomial time. What does this mean? It just means that a computer engineer's ego wont let him accept that he doesn't know how to solve these problem. So, he just says there is no best solution for this class of problem because he can't find one!

Isn't it really very weird?

No comments:

Post a Comment