Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!hplabs!hpda!hpcupt1!mount
From: mount@hpcupt1.HP.COM (John Mount)
Newsgroups: comp.arch
Subject: Re: More math...
Message-ID: <-286679999@hpcupt1.HP.COM>
Date: 16 Jul 89 08:59:04 GMT
References: <5533@pt.cs.cmu.edu>
Organization: Hewlett Packard, Cupertino
Lines: 21

/ hpcupt1:comp.arch / jps@cat.cmu.edu (James Salsman) /  8:10 pm  Jul 14, 1989 /
>Most complexity theory that evaluates the difference
>between regular algorithms and NP-complete algorithms
>seems to be based on turing machines.

Yup.

>Turing machines are the paridigm of serial machines!

Yup.

>How can all these classifications be correct for
>multiprocessors and other parallel machines?

Because unless your parallel processor has an *infinite* number of processors
it is just a big serial machine (by any other name :-).  And if you do have
an infinite amount of processor then NP-complete problems can be solved in
polynomial time on such a beast (so NP-compeleteness becomes a little less
interesting in this case).

John Mount