1994-05-18 - Re: quantum Computing

Header Data

From: juola@bruno.cs.colorado.edu
To: cypherpunks@toad.com
Message Hash: e2c13d2a366e5d42f27c4b3e60d2a9e9d467b6b0341ce67796d4d7e334dc59fe
Message ID: <199405181800.MAA22999@bruno.cs.colorado.edu>
Reply To: N/A
UTC Datetime: 1994-05-18 18:01:10 UTC
Raw Date: Wed, 18 May 94 11:01:10 PDT

Raw message

From: juola@bruno.cs.colorado.edu
Date: Wed, 18 May 94 11:01:10 PDT
To: cypherpunks@toad.com
Subject: Re: quantum Computing
Message-ID: <199405181800.MAA22999@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.
  
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.






Thread