Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!rice!titan!preston
From: preston@titan.rice.edu (Preston Briggs)
Newsgroups: comp.arch
Subject: Re: More math...
Keywords: turing np parallel SIMD MIMD
Message-ID: <4279@kalliope.rice.edu>
Date: 18 Jul 89 02:41:21 GMT
References: <5533@pt.cs.cmu.edu> <898@bnr-rsc.UUCP>
Sender: usenet@rice.edu
Reply-To: preston@titan.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Lines: 26

In article <898@bnr-rsc.UUCP> drago@bnr-rsc.UUCP (Drago Goricanec) writes:
>In article <5533@pt.cs.cmu.edu> jps@cat.cmu.edu (James Salsman) writes:

>>How can all these classifications be correct for
>>multiprocessors and other parallel machines?
>
>If I remember correctly from my Formal Languages class, a parallel machine
>can be simulated by a multi-tape turing machine, which was shown to be
>equivalent to a regular turing machine.  I believe the assumption is

An informal argument is simpler.
Imagine you have a program solving some NP-Complete problem,
say finding a minimal coloring for a graph.
It will take time proportional
to 2^N (where N is number of node in the graph) to run.

If you have a 1000 processor parallel machine
and the program maps with no overhead, you can run
the program 1000 times faster.
However, it's still in time proportional to 2^N.

The point of exponential time is that we can overwhelm
{\em any\/} increase in machine speed by increasing the
problem size by some tiny amount.

Preston