::scr tales from the crypto

[Tom Forwood]

>
> Looks like they're saying that it isn't NP-complete because there's a
> polynomial-time algorithm for it; albeit one that only works on quantum
> computers.  :-)


Quantum computers are able to do all NP problems in polynomial time.  A
non-deterministic computer can miraculously make exactly the right choice at
each branch of execution to fing the write answer.  A quantum computer can
do this by making all possible choices at once.

If anyone ever managed to build a quantum computer it would be able to give
you the answer to problems without even switching it on.

It may even be possible for a quantum computer to do an infinite amount of
computation in a finite time and therefore make the halting problem
computable