Re: quantum Computing
this term keeps poping up recently. Can anybody give me a pointer to where I can find out more info? Someone said that it is nonsense, "quantum computers?, Isn't that something out of a carlos casteneda novel?" I'm just trying to find out the real deal. It's purest bullshit: there are a class of mathematically difficult problems called "NP-Complete". These problems are all equivalent to one another in difficulty, ie if you can solve one you can solve them all (that's where the complete part comes is - 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. 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. It's like trying to guess a 3-bit number, and saying "Is the first bit a 1?" Yes! "Is the second bit a 0?" Yes! "Is the third bit a 0?" Yes! Clearly, in real life, this doesn't happen. However, in fairy-tale land (or quantum physics as it's called) such things *can* happen - because one interpretation of the Einstein-Podolsky-Rosen thought experiment is that every time you make a choice based on the outcome of a quantum event, you fork off a pair of universes! In one universe you make one choice; in the other universe you made the other choice. Consequently if you loose a computer on such a problem, in *one* of the many many universes it generates, it'll find the right answer in polynomial time. The basis of quantum computing as a means to crack NP-complete problems therefore reduces to finding which of these universes found the answer and comminicating that answer to all the other universes. (Of course, you don't have to do this part, but the 99.9999999999999999999999999999999% of experimenters in all the universes that didn't find the result are not going to believe the method words too well...) Basically, it's a theoretical result with no application in the real world, and if ever anything happens that makes it mappable to the real world we'll have been subjected to such a major upheaval in the way the universe works that no-one will give a damn any more about such trivial things as encryption because we'll all effectively have turned into magicians :-) G
Rick Busdiecker writes:
Not true. What that means is that a polynomial time solution exists for an NFA. The only part has not been shown.
While we're being picky, I'll point out that (unless I'm wrong of course) it's not really an NFA, but a non-deterministic Turing machine (an "NTM"?) that's the automaton at issue here. -- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
Rick Busdiecker writes:
No, NFA is acceptable and correct, it's Non-determinisic Finite Automaton. A non-deterministic Turing machine is a perfectly reasonable example, however.
Uhh, isn't it the case that a Turing machine can simulate an NFA, but not the reverse? An NFA has no tape, and therefore is not as powerful an automaton as a Turing machine. Thus an NFA can be implemented by an NTM, but not the reverse. I think. -- | GOOD TIME FOR MOVIE - GOING ||| Mike McNally <m5@tivoli.com> | | TAKE TWA TO CAIRO. ||| Tivoli Systems, Austin, TX: | | (actual fortune cookie) ||| "Like A Little Bit of Semi-Heaven" |
Mike McNally says:
Rick Busdiecker writes:
No, NFA is acceptable and correct, it's Non-determinisic Finite Automaton. A non-deterministic Turing machine is a perfectly reasonable example, however.
Uhh, isn't it the case that a Turing machine can simulate an NFA, but not the reverse? An NFA has no tape, and therefore is not as powerful an automaton as a Turing machine. Thus an NFA can be implemented by an NTM, but not the reverse.
I think.
Correct. The hierarchy as I remember it is roughly (from least to most powerful in terms of size of the recognizable languages) FAs, PDAs (that is, deterministic push-down automata), NPDAs, TMs. Its been a while, but I seem to recall that non-deterministic pushdown automata could recognise some languages that deterministic ones could not. Perry
-----BEGIN PGP SIGNED MESSAGE----- Date: Wed, 18 May 1994 14:14:41 -0400 From: "Perry E. Metzger" <perry@imsi.com> Its been a while, but I seem to recall that non-deterministic pushdown automata could recognise some languages that deterministic ones could not. Yes, that's correct. Rick -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLdpcUxaZNKPPNj41AQHRRQQAjzRo7nSxd5meEjSoExGUhJJSQ2H63wEZ VDlZ9627j7kAVZHGvM0H6JNeN5IIgRX7hv2cruZwE8Gm49bZxE/iEgOLA1p0/IK+ T31BzIEebccwbKYF97Ndnf3kFHD36XVL8QEVJ09yGHjX7uyL5Vd2Gk7cb8ljp3JU C3QX3YTB4FU= =sV/8 -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Date: Wed, 18 May 94 13:03:43 CDT From: m5@vail.tivoli.com (Mike McNally) An NFA has no tape . . . Mine does :-) It's a matter of definition, I suppose. Hopcroft and Ullman describe an NFA as having a tape. On the other hand, they also descript the NP Completeness in terms of an NTM, so I'll concede your point. Rick -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLdpbIRaZNKPPNj41AQHG+gQAtYMYanQzNIYeWV8DlIr+LAT8Lu7UNZWD DzZMa30vlliUU9twWZW23fiQltWKGx0GG73IG3egLJ01Qeo1t7aN6Dl20+Jm2CIQ xDxOrQc+I+rakSW4/MmC5PgfoXazKTtF3X+BaRXdkfZqvH0Lt9hvzaEJ0nA43iG9 YIpXYDesqcc= =/Plo -----END PGP SIGNATURE-----
From: Rick Busdiecker <rfb@lehman.com> It's a matter of definition, I suppose. Hopcroft and Ullman describe an NFA as having a tape.
I find this a little odd, given that the "F" stands for "finite". Checking Hopcroft and Ullman, they define an NFA formally as a tuple: states, inputs, initial state, final states, and a mapping from states cross inputs to 2^states. No tape. Eli ebrandt@hmc.edu
-----BEGIN PGP SIGNED MESSAGE----- I was in a hurry and misread something to be supporting something else that I had misremembered. I apologize for not being more careful and I continue to concede the point that NP completeness is defined in terms of NTMs rather than NFAs. FWIW, what I misread was a blurb near the front of Formal Languages and Finite Automata (I'm guessing at the title, the book is no longer near by) H&U simply described the input to the machine as a tape. Rick -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLdq6lBaZNKPPNj41AQH/EAP/eZlxtjQbzlsVssKmY9n7Smh0bGwgVPQr tQ8mhBBQFPeByTR24wPp2qINws8WgzDI9EOTnrkSxs0NI6Ig3uusXxHEdPfhUfnl kO2uTgAJ/pFztQXyvCIkGyAs0RlthLaatpquZFue07r2JFOo0AB7XG6CprF9kvGH eTjfWvb+Ygo= =BUsf -----END PGP SIGNATURE-----
-----BEGIN PGP SIGNED MESSAGE----- Date: Wed, 18 May 94 12:46:46 CDT From: m5@vail.tivoli.com (Mike McNally) While we're being picky, I'll point out that (unless I'm wrong of course) it's not really an NFA, but a non-deterministic Turing machine (an "NTM"?) that's the automaton at issue here. No, NFA is acceptable and correct, it's Non-determinisic Finite Automaton. A non-deterministic Turing machine is a perfectly reasonable example, however. Rick -----BEGIN PGP SIGNATURE----- Version: 2.3a iQCVAgUBLdpWthaZNKPPNj41AQEttwQAnCs9sZ+fV9BhCMf/PXyM6w59NjIc8ZwF vVL394XfzqvQKUzwK8pV04d5YMusfgbVibj+IuEaAEkn9qMYkaoX9XL65tzhPf8N 6bilBkRVIuCmLye9J0vpylouqS7bAakF7Htu06EDOzTQArBXEWUaBGkaH5P+m8xu xQLMS1RmmKk= =H5dW -----END PGP SIGNATURE-----
Rick Busdiecker says:
From: m5@vail.tivoli.com (Mike McNally)
While we're being picky, I'll point out that (unless I'm wrong of course) it's not really an NFA, but a non-deterministic Turing machine (an "NTM"?) that's the automaton at issue here.
No, NFA is acceptable and correct, it's Non-determinisic Finite Automaton. A non-deterministic Turing machine is a perfectly reasonable example, however.
A turing machine is not a finite automaton -- it has an infinite tape. Perry
-----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-----
participants (5)
-
Eli Brandt -
gtoal＠an-teallach.com -
m5＠vail.tivoli.com -
Perry E. Metzger -
Rick Busdiecker