[Haskell-cafe] Re: Wikipedia on first-class object
ajb at spamcop.net
ajb at spamcop.net
Sun Dec 30 05:15:35 EST 2007
G'day all.
I think it was Ketil Malde who said:
>> If I understand correctly, a quantum computer might solve problems in
>> NP in polynomial time, which is assumed not to be possible for
>> deterministic computers.
Quoting Miguel Mitrofanov <miguelimo38 at yandex.ru>:
> No! Moreover, there is a hypothesis that the only problems quantum
> computer can solve in polynomial time are those that the usual computer
> can.
"Problems in NP" is not the same as "NP-hard". We know that a quantum
computer can solve problems in NP in polynomial time, since every
problem in P is also in NP. Moreover, we know of at least one problem
not known to be in P which can be sort-of solved by a quantum computer in
polynomial time (prime factoring). In that sense, the "understanding" is
more or less correct.
But yeah, it seems likely that the best that a quantum computer can do
is bring "almost intractable" problems down to "barely tractable".
Cheers,
Andrew Bromage
More information about the Haskell-Cafe
mailing list