-----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 Completeness problem. Date: Wed, 18 May 1994 17:47:34 +0100 From: gtoal@an-teallach.com (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 make. 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 :-) Rick -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLdpS7RaZNKPPNj41AQE6qAQAueihy10qYc5HCeJ1Fx2WbR8mvxfRc94i FK7zkHv916Uo2dPfwnldDvapUAamkALiPpTJ6+6g8L/XuLB+rOc9Nwrzs5WzjVgN KNKSZ5dN8Fa21RB1gd9jD/hC3ND1Fz/HyYOi6fMtzMFqh08nC27e4C4CDL+QqpHG glCM7qMVOIY= =0lM1 -----END PGP SIGNATURE-----