17 Dec
2003
17 Dec
'03
11:17 p.m.
When I first heard about P and NP and such, I made a common mistake, one which I think underlies a lot of the misconceptions people have. I knew that P meant "polynomial time" and understood pretty well what that meant, but I mistakenly jumped to the conclusion that NP meant "non-polynomial time", the complement of P. It does not, of course; it means "nondeterministic polynomial time" as others have described. Basically, if you could _check_ an answer to a problem in polynomial time the problem is in NP, as others have described here. Hal