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 <[EMAIL PROTECTED]>:
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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
