Article View: comp.arch
Article #1538Re: More math...
From: John Mount
Date: Sun, 16 Jul 1989 08:59
Date: Sun, 16 Jul 1989 08:59
21 lines
1123 bytes
1123 bytes
/ 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
Technical Details
Message-ID:
<-286679999@hpcupt1.HP.COM>Path:
arc1-ca.pugleaf.net!utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!hplabs!hpda!hpcupt1!mountReferences:
<5533@pt.cs.cmu.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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