From: hughes@ah.com (Eric Hughes)
Date: Wed, 30 Mar 94 12:31:37 PST
To: cypherpunks@toad.com
Subject: Crypto and new computing strategies
In-Reply-To: <199403301930.AA19134@access2.digex.net>
Message-ID: <9403302016.AA00316@ah.com>
MIME-Version: 1.0
Content-Type: text/plain


>Analog computers have very different behaviors than
>digital computers. 

But these difference are differences in constant factors of
computation, not of computational expressibility.

>Some guys have also build an analog machine that can
>solve 3SAT problems in linear time. They surmise, though,
>that the machine must be built with precision that is
>exponential in the number of terms. I.e. it won't work. 

You can design an infinite family of finite circuits which do 3SAT in
linear time as well.  The only problem is that it takes an
exponentially increasing number of gates.  It's exactly the same
asymptotic effect, which, as you should all know by now, comes as no
surprise to me.

>I would assume that any QM machines will _not_ be 
>exclusively digital. This is the easiest programming
>model, but someone may come up with a better one. 

I don't anticipate QM machines will be deterministic, but they
certainly will be bounded in the expected sizes of their state spaces.
This will make them simulable by, and therefore equivalent to,
probabilistic Turing machines.  A significant number of real-life
crypto algorithms are already using this model (like primality
testing), so there's no advantage in the computational model.

Eric