From: Rick Busdiecker <rfb@lehman.com>
Date: Wed, 18 May 94 10:40:55 PDT
To: gtoal@an-teallach.com (Graham Toal)
Subject: Re: quantum Computing
In-Reply-To: <199405181647.RAA02357@an-teallach.com>
Message-ID: <9405181740.AA14304@fnord.lehman.com>
MIME-Version: 1.0
Content-Type: text/plain


-----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-----