Subject: Scientific American

From: Joseph Traub <[email-masked]>
Date: Wed, 5 Jan 94 9:18:37 EST

The cover story in the January 1994 issue of Scientific American titled
"Breaking Tractability" is by Traub and Wozniakowski. Its shown how some
computationally intractable problems can be solved if one settles for a
gtood solution most but not all of the time.

An example of such a problem is high dimensional integration, which
must often be solved when one seeks the expected value of a stochastic
process. The current method of choice for computing a high dimensional
integral is Monte Carlo. Theory indicates that certain deterministic 
algorithms are better than Monte Carlo. Preliminary results of software
testing by a PhD student, Spassimir Paskov, support the superiority
of certain deterministic algorithms. The tests have been run on 
integrals of dimension as high as 360.

We would be grateful to receive high dimensional integration or
approximation problems from diverse applications.

In the final part of the article we suggest there might be provable
limits to scientific knowledge.