🚀 go-pugleaf

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