|
(other people have answered you already, and their answers seem quite knowledgeable, but I sense their answers are actually off the point of your question, i.e. I think there is a better answer than you have been given. However, I learned this material long time ago and the precise answer is not fresh in my mind, so hopefully I can give you the gist, we'll see, but apologies in advance for all my hand waving) it's like this: if I give you a large number and say "factor this", you will work hard figuring out the answer, but if I give you a set of factors and say multiply them together and see if they equal the big number, you can do that fairly quickly. i.e. you can check the answer a lot easier than you can find the answer. An NP complete optimal routing problem is the same way, it's hard to find an answer, but if somebody gives you the optimal solution, it is easy to check that it is optimal by substituting segments from the solution set for segments that are not in the solution set, and trying to incrementally improve on it: if you have a solution, none of your substitutions will piece-wise be an improvement, furthermore, you can do it in an orderly way that "proves" your route is best precisely without duplicating all your work. This is the part I don't remember but it's something like "find the longest segment on your route, is there some shorter way to accomplish what that accomplishes? no there isn't. or look at the shortest segments, are they penny-wise but pound-foolish, no they aren't." i.e. the part I do remember is that it is polynomial time to confirm the answer, and it is not polynomial time to find the answer. This is what is in fact meant by "non-deterministic polynomial", it's polynomial only if you magically know the answer in a non-deterministic way. Polynomial to check, but in a deterministic way it is not polynomial to determine. Again, sorry for all the handwaving, but I'm pretty certain that's right. Oh, and while I'm here, what was the most irritating thing about this article is that P vs NP is not a huge "assumption". Call it a conjecture, call it a hypothesis, call it a problem to solve, but it's not an assumption, it's been tested long and hard by a lot of really smart people and it's the fringes of our knowledge. That's not what is typically meant by the word "assumption". |