Re: Quantum Computer Algorithms

From: Esa A E Peuha (esa.peuha_at_helsinki.fi)
Date: 09/28/04 

Date: Tue, 28 Sep 2004 16:50:53 +0000 (UTC)

peterwshor@aol.com (Peter Shor) writes:

> As far as I know, Turing did not
> consider quantum mechanics to be relevant when he formulated Turing
> machines---a remarkable accomplishment nonetheless.

In fact, Turing's motivation was to find out exactly what a human
following an algorithm could do, and after he eliminated everything that
was irrelevant, he had the definition of a Turing machine.

> *(to be pedantic, if factoring is NP-complete, than NP = co-NP, something
> which theoretical computer scientists don't generally think is true).

More importantly, while factoring is not known to be in P, the
corresponding decision problem (is a number prime or composite) _is_
known to be in P, whereas for all known NP-complete problems the search
and decision problems are complexity equivalent (and probably must be
for every NP-complete problem). 

-- 
Esa Peuha
student of mathematics at the University of Helsinki
http://www.helsinki.fi/~peuha/