Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site ssc-vax.UUCP
Path: utzoo!linus!decvax!microsoft!uw-beaver!ssc-vax!sts
From: sts@ssc-vax.UUCP (Stanley T Shebs)
Newsgroups: net.ai
Subject: Re: NP-completeness and parallelism
Message-ID: <384@ssc-vax.UUCP>
Date: Mon, 8-Aug-83 16:30:54 EDT
Article-I.D.: ssc-vax.384
Posted: Mon Aug  8 16:30:54 1983
Date-Received: Tue, 9-Aug-83 15:27:45 EDT
References: <3894@sri-arpa.UUCP>
Organization: Boeing Aerospace, Seattle
Lines: 13

Parallel machines buy you speed improvements at the cost of space.
As an example, a reduction machine of the style being worked on by
Gyula Mago (at either unc or ncsu - don't remember) using some
variation on the Backus FP language would be very fast.  It could
multiply two NxN matrices in log N time - but would require N**4
processors (=space) to achieve this performance!  This is not really
bad; it's certainly better than having to build machines that use
X-rays for the system clock :-) .  It does mean that algorithm
analysis is always going to be useful, no matter how good the
hardware is.

					stan the lep hacker
					ssc-vax!sts (soon utah-cs)