[13870] in Cypherpunks
Re: quantum Computing
daemon@ATHENA.MIT.EDU (Mike McNally)
Wed May 18 13:54:52 1994
Date: Wed, 18 May 94 12:46:46 CDT
From: m5@vail.tivoli.com (Mike McNally)
To: Rick Busdiecker <rfb@lehman.com>
Cc: cypherpunks@toad.com
In-Reply-To: <9405181740.AA14304@fnord.lehman.com>
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" |
