Hacker News Reader

Comment by odonnellryan | Hacker News Reader

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?

View on HN

I 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?

No, 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.

Reply on news.ycombinator.com