[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: ::scr tales from the crypto
> 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