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