[13872] in Cypherpunks
Re: quantum Computing
daemon@ATHENA.MIT.EDU (juola@bruno.cs.colorado.edu)
Wed May 18 14:09:55 1994
To: cypherpunks@toad.com
In-Reply-To: Your message of Wed, 18 May 94 12:46:46 CDT
Date: Wed, 18 May 94 12:00:47 MDT
From: juola@bruno.cs.colorado.edu
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.
Mike McNally responds:
>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.
That is correct. As a matter of fact, it's an easy theorem that
an NFA has the same computing capacity as a DFA; it is not known
whether this theorem holds for more powerful machines, and is in
fact the heart of the P ?= NP conjecture.
