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 and parallelism
Message-ID: <3894@sri-arpa.UUCP>
Date: Fri, 5-Aug-83 17:06:06 EDT
Article-I.D.: sri-arpa.3894
Posted: Fri Aug  5 17:06:06 1983
Date-Received: Sun, 7-Aug-83 02:11:51 EDT
Lines: 19

From:  David Rogers <DRogers@SUMEX-AIM.ARPA>

        In AIList V#32 Fred comments that "NP-completeness cannot be 
gotten around in general by building bigger or faster computers".  My
guess would be that parallelism may offer a way to reduce the order of
an algorithm, perhaps even to a polynomial order (using a machine with
"infinite parallel capacity", closely related to Turing's machine with
"infinite memory"). For example, I have heard of work developing 
sorting algorithms for parallel machines which have a lower order than
any known sequential algorithm.

        Perhaps more powerful machines are truly the answer to some of
our problems, especially in vision analysis and data base searching.  
Has anyone heard of a good book discussing parallel algorithms and 
reduction in problem order?

David Rogers

DRogers@SUMEX-AIM.ARPA