From: collins@newton.apple.com (Scott Collins)
Date: Tue, 19 Jul 94 16:17:07 PDT
To: cypherpunks@toad.com
Subject: Non-determinism forever. (was -- Re: GUT and P=NP)
Message-ID: <9407192254.AA27028@newton.apple.com>
MIME-Version: 1.0
Content-Type: text/plain


At  9:58 PM 18.7.94 -0700, Eric Hughes wrote:
  >Non-determinism is only another way of rephrasing the existential
  >quantification.

I agree.

Entropy, like velocity, is relative.  `Non-deterministic' is the label we
apply to the unknown or possibly unknowable.  Non-deterministic algorithms
(or thought experiments) work by `knowing more than we do'.  They guess the
un-guessable: the correct answers to problems we can't solve readily any
other way.  From their point of view, for some reason, it's not
un-guessable.  This very attribute makes them un-guessable to us.

We simulate `guessing' correctly by exhaustive search (check out, e.g.,
NFA's and pattern matching).  "Is P==NP?" is roughly equivalent to "For
every problem that you could `guess' the answer if only you knew how---and
can prove the answer correct without guessing---is there a shortcut (that
meets some strong criterea)?"

If P==NP is ever proven it _will_ have an impact on a large class of
problems (and the effect will depend on the nature of the proof), but not
all problems.  Some problems are harder than NP, e.g. decrypting a message
encrypted with a truly random OTP.  Even if you guess the correct
decryption, you can't prove it's right without guessing.

Currently, lacking `THE shortcut', P != NP (in the practical sense; _not_
the theoretical).  Even if it becomes the case that, demonstrably, P == NP
in both the practical and theoritical sense, the world will still be an
interesting place (in both the practical and theoretical sense).


Scott Collins     | "Invention, my dear friends, is 93% perspiration,
                  |  6% electricity, 4% evaporation, and 2% butter-
  collins@acm.org |  scotch ripple."                   -- Willy Wonka
..................|..................................................
Apple Computer, Inc.  5 Infinite Loop, MS 305-2D  Cupertino, CA 95014
408.862.0540   fax:974.6094   R254(IL5-2N)   collins@newton.apple.com
.....................................................................
408.257.1746  1024:669687                         catalyst@netcom.com