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