3 ms·
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
by dgacmu 9y ago
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?