From: juola@bruno.cs.colorado.edu
Date: Wed, 18 May 94 11:10:34 PDT
To: cypherpunks@toad.com
Subject: Re: quantum Computing
Message-ID: <199405181810.MAA23216@bruno.cs.colorado.edu>
MIME-Version: 1.0
Content-Type: text/plain


    
    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.
    
  and I then gibbered :
  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.


Whups.  Teach me to post before eating breakfast....  Ignore what
I just said above.

	- kitten