DRogers@SUMEX-AIM.ARPA@sri-unix.UUCP (08/09/83)
From: David Rogers <DRogers@SUMEX-AIM.ARPA>
I forward this message because it raises an interesting point, and
I thought readers may care to see it. I had a reply to this, but
perhaps someone else may care to comment.
Date: Sun, 7 Aug 83 18:28:09 CDT
From: Mike.Caplinger <mike.rice@Rand-Relay>
Claiming that a parallel machine makes NP-complete problems
polynomial (given that the machine has an infinite number of
processing elements) is certainly true (by the definition of
NP-completeness), but meaningless. Admittedly, a large number of
processing elements might make a finitely-bounded algorithm faster,
but any finitely-bounded algorithm is a constant time algorithm.
(If I say N is never greater than the number of processors, then N
might as well be a constant.)