From: collins@newton.apple.com (Scott Collins)

To: cypherpunks@toad.com

Message Hash: 916d26b4d32bf93a2afda17d3de0da270eae343c4a01dbbaf9fa9cd29336f0ba

Message ID: <9407192254.AA27028@newton.apple.com>

Reply To: *N/A*

UTC Datetime: 1994-07-19 23:17:07 UTC

Raw Date: Tue, 19 Jul 94 16:17:07 PDT

```
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
```

Return to July 1994

Return to “collins@newton.apple.com (Scott Collins)”

1994-07-19 (Tue, 19 Jul 94 16:17:07 PDT) - Non-determinism forever. (was – Re: GUT and P=NP) -

*collins@newton.apple.com (Scott Collins)*