Non-determinism forever. (was -- Re: GUT and P=NP)

Hal hfinney at shell.portal.com
Wed Jul 20 16:35:02 PDT 1994


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






More information about the cypherpunks-legacy mailing list