[13906] in Cypherpunks
Re: quantum Computing
daemon@ATHENA.MIT.EDU (Rick Busdiecker)
Wed May 18 21:10:41 1994
To: Eli Brandt <ebrandt@jarthur.cs.hmc.edu>
Cc: cypherpunks list <cypherpunks@toad.com>
In-Reply-To: Your message of "Wed, 18 May 1994 14:55:28 PDT."
<9405182155.AA08254@toad.com>
From: Rick Busdiecker <rfb@lehman.com>
Reply-To: Rick Busdiecker <rfb@lehman.com>
Date: Wed, 18 May 1994 21:02:17 -0400
-----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-----
