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