GUT and P=NP

Eric Hughes hughes at ah.com
Mon Jul 18 22:22:19 PDT 1994


   question struck me:  If a Grand Unified Theory exists, would it not 
   prove P=NP to be true?

No.  Hardly.

   behaviour we believe to be non-deterministic
   really isn't: it obeys the GUL.  So P=NP must be true, since NP is
   an artifact our pre-GUL way of looking at things.

Non-determinism will exist forever as an idea, just the same way that
no real number has ever been measured, merely approximations to them.
NP is an expression of that idea.  There are other ways to formalize
NP without resorting to non-determinism.  NP is the class of problems
for which there exists a witness to a PTIME computation.
Non-determinism is only another way of rephrasing the existential
quantification.

Eric






More information about the cypherpunks-legacy mailing list