Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!decvax!harpo!seismo!hao!hplabs!sri-unix!DRogers@SUMEX-AIM.ARPA
From: DRogers@SUMEX-AIM.ARPA@sri-unix.UUCP
Newsgroups: net.ai
Subject: NP-completeness
Message-ID: <4247@sri-arpa.UUCP>
Date: Mon, 8-Aug-83 20:19:42 EDT
Article-I.D.: sri-arpa.4247
Posted: Mon Aug  8 20:19:42 1983
Date-Received: Thu, 18-Aug-83 06:01:34 EDT
Lines: 17

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.)