Urg... I think I know why I'm confused. P, NP, etc... are sets of yes/no or boolean problems. That is to say, the answer to these questions are always "Yes" o

Urg... I think I know why I'm confused. P, NP, etc... are sets of yes/no or boolean problems. That is to say, the answer to these questions are always "Yes" or "No". Lets take the traveling saleperson problem. You have a bunch of cities, and the distances between them. Also, your given a threshold, K. Your goal is to tell me if there is a path through the cities that has a distances less than K. All you output is "Yes" or "No" This can be converted to an algorithm for finding the shortest path in polynomial time, which is the optimization version of the problem. But this problem is not in NP, its not even a candidate to be in NP. However, I'm having trouble relating to what your saying. > A possible solution can be found in P time. But checking if it's THE solution (i.e. the best solution) requires NP time. In terms of traveling salesperson, what is "a possible solution" and what is "the solution"? I'm guessing "the solution" is the shortest path, but if "a possible solution" means some path through all the cities... then that doesn't help much. Even for problems that are harder than NP, I can come up with a possible solution in polynomial time as long as the size of the solution is polynomial (I'm having difficulty thinking up an example at the moment). Tell me if I'm being hard-headed or overly semantic...