Path: utzoo!bnr-vpa!bnr-rsc!drago
From: drago@bnr-rsc.UUCP (Drago Goricanec)
Newsgroups: comp.arch
Subject: Re: More math...
Keywords: turing np parallel SIMD MIMD
Message-ID: <898@bnr-rsc.UUCP>
Date: 17 Jul 89 22:22:47 GMT
References: <5533@pt.cs.cmu.edu>
Reply-To: drago@bnr-rsc.UUCP (Drago Goricanec)
Organization: Bell-Northern Research, Ottawa, Canada
Lines: 24

In article <5533@pt.cs.cmu.edu> jps@cat.cmu.edu (James Salsman) writes:
>
>Most complexity theory that evaluates the difference
>between regular algorithms and NP-complete algorithms
>seems to be based on turing machines.
>
>Turing machines are the paridigm of serial machines!
>
>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
that the number of tapes must be finite, since there must be a finite
number of letters in the tape alphabet.  This would imply that the
NP-complete algorithms are also correct for parallel machines given
that the number of multiprocessors is finite.

P.S.  Please don't flame if I got anything wrong, just point me
in the right direction.
-- 
Drago Goricanec                              (...!bnr-vpa!bnr-rsc!drago)
Bell-Northern Research Ltd., Ottawa, Ontario              (613) 763-8957