[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: quantum Computing
-----BEGIN PGP SIGNED MESSAGE-----
Disclaimer: I'd never even heard of a quantum machine until quite
recently and I have no idea how they relate to the NP
Date: Wed, 18 May 1994 17:47:34 +0100
From: [email protected] (Graham Toal)
. . . it's NP-complete if you can prove that equivalence to
another NP-complete problem).
The "NP" part is "Non-deterministic, polynomial time". What that means
is that there is a solution possible in polynomial time (rather than
exponential time) *ONLY* on a *NON-DETERMINISTIC* machine.
Not true. What that means is that a polynomial time solution exists
for an NFA. The only part has not been shown.
And that's the fun part, because a non-deterministic machine is
one that *guesses* the correct path every time it has a choice to
That's one way of viewing it, well close anyway. Typically it's
described as guessing the correct path and then verifying its
correctness. Another, equally valid way to view a non-deterministic
machine is as one which executes all paths simultaneously.
Clearly, in real life, this doesn't happen.
Perhaps. In any case, if you have a proof that the NP-Complete
problems cannot be done in polynomial time on a deterministic machine,
by all means, please share it with us . . . and collect your prize :-)
-----BEGIN PGP SIGNATURE-----
-----END PGP SIGNATURE-----