Scientific American article

[David Farber <farber@central.cis.upenn.edu>]

Date: Tue, 4 Jan 94 11:22:28 EST
From: Joseph Traub <traub@cs.columbia.edu>
To: farber@central.cis.upenn.edu
Subject: Scientific American


The cover story in the January 1994 issue of Scientific American titled
"Breaking Intractability" is by Traub and Wozniakowski. It consists of
two parts. First its shown how some computationally intractable problems
can be solved if one settles for a good solution most but not all of the
time.


An example of such a problem is high dimensional integration, which must
be solved whenever one seeks the expected value of a stochastic process.
The method of choice for computing integrals is Monte Carlo. Preliminary
results of software testing by a Phd student, Spassimir Paskov, indicates
that deterministic methods are superior to Monte Carlo. To date, this
testing has been primarily on real-world problems in finance.


In the second part of the article we suggest that there might be provable
limits to scientific knowledge