1994-07-22 - Re: GUT and P=NP

Header Data

From: jamesd@netcom.com (James A. Donald)
To: m5@vail.tivoli.com (Mike McNally)
Message Hash: 085198b826540c8f69bd93e7dfbbbbf21d3a89a71d60a4a91a675015f29c2989
Message ID: <199407220328.UAA19260@netcom5.netcom.com>
Reply To: <9407211244.AA16861@vail.tivoli.com>
UTC Datetime: 1994-07-22 03:28:02 UTC
Raw Date: Thu, 21 Jul 94 20:28:02 PDT

Raw message

From: jamesd@netcom.com (James A. Donald)
Date: Thu, 21 Jul 94 20:28:02 PDT
To: m5@vail.tivoli.com (Mike McNally)
Subject: Re: GUT and P=NP
In-Reply-To: <9407211244.AA16861@vail.tivoli.com>
Message-ID: <199407220328.UAA19260@netcom5.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


Mike McNally writes
> 
> 
> James A. Donald writes:
>  > Existing physical theories show that Super Turing machines are
>  > possible in principle though very difficult to build in practice.
> 
> That's the understatement of the year.

I was referring to the proposed quantum computers.

> 
>  > 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.
> 
> Huh?
> 
>  > Since such machines do not operate algorithmically
> 
> This statement is exactly wrong.  Such machines *define* a class of
> algorithms.

I recommend that you read the following paper.

E. Bernstein and U. Vazirani, {\it Quantum Complexity
Theory}, Proc. 25th ACM Symp. on Theory of Computation, pp.  11--20
(1993).


-- 
 ---------------------------------------------------------------------
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@netcom.com





Thread