X-Message-Number: 4269
From: Peter Merel <>
Subject: CRYONICS Complexity
Date: Fri, 21 Apr 1995 23:02:20 +1000 (EST)

Paul Wakfer writes,

>     Whatever the theoretical considerations, if you have one computer
>which produces a result in 10,000 units of time and another, using the same
>level of technology, which produces the same result in 1 unit of time
>because there are upwards of 10,000 of them working in parallel, then
>unless (and until) technology advances (ie. reality - physical law - does
>not prevent it from so doing) so that the 1 unit of time is below the
>perceptive or even the measurement threshold of humans (so that the 1 and
>10,000 may be perceptively very close), then I maintain there *is* a
>*fundamental* difference between these computers in the sense that they can
>have radically different effects on reality.

Quite so. However the disclaimer you include, that "the 1 and 10,000 may be
perceptively very close" is the reason that we categorise various problems
according to their computational complexity; computationally complex problems
defy general solution by simple technological progression. Dramatic 
technological improvements, such as quantum computers, might be another story.

>Whatever response this generates, I state, in advance, that I will not
>reply.

Many apologies if my earlier reply gave any offence; that certainly was
not my intention. 

Keith Lynch writes,

>Peter Merel <>
>> ... but which can be solved in polynomial time on a non-deterministic
>> (read "parallel") machine.
>
>Non-deterministic is not the same as parallel.
>
>Parallel computers (including neural nets) are parallel and
>deterministic.  If a problem can't be solved in polynomial time on a
>serial machine, then it can't be solved in polynomial time on a parallel
>machine either.

Quite so; you may see later in the same article I suggest that neural
nets are not non-deterministic automata for just this reason. I guess I
have a small exception to note in this: if the number of processors in
a parallel machine could be made to increase without bound faster than 
the rate indicated by the computational complexity of the problem at hand, 
then for most purposes we could say that this parallel architecture is
non-deterministic. However there are problems in abundance for which 
such any such architecture would consume all available materials with
which to implement itself ...

Peter Merel.


Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=4269