From: Hal <hfinney@shell.portal.com>
Date: Wed, 20 Jul 94 16:35:02 PDT
To: cypherpunks@toad.com
Subject: Re: Non-determinism forever. (was -- Re: GUT and P=NP)
Message-ID: <199407200447.VAA01776@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


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