GUT and P=NP

James A. Donald jamesd at netcom.com
Wed Jul 20 17:49:56 PDT 1994


Timothy C. May writes
> Another way to put it, there is no evidence, despite some speculation
> by Peter Shor, David Deutsch, Roger Penrose, and others, that any new
> theories of physics will allow "Super-Turing machines" to be built. In
> fact, most physicists discount this kind of speculation. 

Existing physical theories show that Super Turing machines are possible
in principle though very difficult to build in practice.

Such machines will probably not be able to solve NP complete
problems though they will be able to solve some NP problems
such as factoring.

Since such machines do not operate algorithmically, they have
no relevance to the question of whether P=NP, because this
question is a question about *algorithms*.

-- 
 ---------------------------------------------------------------------
We have the right to defend ourselves and our
property, because of the kind of animals that we              James A. Donald
are.  True law derives from this right, not from
the arbitrary power of the omnipotent state.                jamesd at netcom.com






More information about the cypherpunks-legacy mailing list