5 ms·
Isn't it a little misleading to say a problem is NP "if I can give you a solution to it and you can easily verify that the solution is correct." Not all proble
by odonnellryan 9y ago
Isn't it a little misleading to say a problem is NP "if I can give you a solution to it and you can easily verify that the solution is correct."
Not all problems that fit that description fall into NP, right?
- dgacmu 9y agoI can only think of a few ways in which my definition fails. First, that it doesn't identify that NP only requires polytime verifiability for satisfying answers, not for "no" answers; second, that the use of the informal "you" instead of "a deterministic Turing machine" makes assumptions about the bounds of human reasoning that I assume are correct but don't know for certain; and third, that the ease of verifying certain solutions may mislead a lay-observer into thinking that a problem is in NP when, in fact, it is harder. ("This program exits because it consists only of the single statement exit(0);"). I think the third problem with my definition is the most thorny. But if you take the technically accurate form form of it that doesn't risk confusing easy instances with worst-case behavior - that you can verify in polytime a solution to any instance of the problem - it's technically correct. But which things did you have in mind, and how would you improve the explanation?
- popcorncolonel 9y agoNo, that's what NP means. Given a witness to a solution of a problem, verifying that the solution is correct in polynomial time means the problem is in NP.