Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site pyuxll.UUCP
Path: utzoo!linus!decvax!harpo!gummo!whuxlb!pyuxll!ech
From: ech@pyuxll.UUCP (Ned Horvath)
Newsgroups: net.ai
Subject: Re: NP-completeness and parallelism
Message-ID: <388@pyuxll.UUCP>
Date: Sun, 7-Aug-83 16:57:17 EDT
Article-I.D.: pyuxll.388
Posted: Sun Aug  7 16:57:17 1983
Date-Received: Mon, 8-Aug-83 01:32:55 EDT
References: <3894@sri-arpa.UUCP>
Organization: American Bell, South Plainfield NJ
Lines: 42

A couple of clarifications are in order here:

1. NP-completeness of a problem means, among other things, that the
	best known algorithm for that problem has exponential
	worst-case running time on a serial processor.  That is not
	intended as a technical definition, just an operational one.
	Moreover, all NP-complete problems are related by the fact
	that if a polynomial-time algorithm is ever discovered for
	any of them, then there is a polynomial-time algorithm for
	all, so the (highly oversimplified!) definition of NP-complete,
	as of this date, is "intrinsically exponential."

2. Perhaps obvious, but I will say so anyway: n processors yoked in
	parallel can't do better than to be n times faster than a
	single serial processor. For some problems (e.g. sorting),
	the speedup is less.

The bottom line is that the "biggest tractable problem" is proportional
to the log of the computing power at your disposal; whether you increase
the power by speeding up a serial processor or by multiplying the number
of processors is of small consequence.

Now for the silver lining.  NP-complete problems often can be tweaked
slightly to yield "easy" problems; if you have an NP-complete problem
on your hands, go back and see if you can restrict it to a more readily
soluble problem.

Also, one can often restrict to a subproblem which, while it is still
NP-complete, has a heuristic which generates solutions which aren't
too far from optimal.  An example of this is the Travelling Salesman
Problem.  Several years ago Lewis, Rosencrantz, and Stearns at
GE Research described a heuristic that yielded solutions that were
no worse than twice the optimum if the graph obeyed the triangle
inequality (i.e. getting from A to C costs no more than going from
A to B, then B to C), a perfectly reasonable constraint.  It seems
to me that the heuristic ran in O(n-squared) or O(n log n), but
my memory may be faulty; low-order polynomial in any case.

So: "think parallel" may or may not help.  "Think heuristic" may
help a lot!

=Ned=