cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

1994-07-19 - GUT and P=NP

Header Data

From: hughes@ah.com (Eric Hughes)
To: cypherpunks@toad.com
Message Hash: 6bcb665fa94cafa9923b1cb8454e9e0fe5320f652354f296179b48427305a744
Message ID: <9407190458.AA23116@ah.com>
Reply To: <199407190029.AA07438@world.std.com>
UTC Datetime: 1994-07-19 05:22:19 UTC
Raw Date: Mon, 18 Jul 94 22:22:19 PDT

Raw message

From: hughes@ah.com (Eric Hughes)
Date: Mon, 18 Jul 94 22:22:19 PDT
To: cypherpunks@toad.com
Subject: GUT and P=NP
In-Reply-To: <199407190029.AA07438@world.std.com>
Message-ID: <9407190458.AA23116@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


   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

Thread