Settling for Good Enough
Both DNA computing and quantum computing reach into the physical
universe for assistance in solving a mathematical problem. This is the re-
verse of the way matters usually proceed—normally, mathematics is used
to solve a problem in the physical universe. Barring a bolt from the blue in
the form of a Clay Millennium Prize, the most useful approach is to de-
velop approximate solutions—as we have seen, this is an important area in
applied mathematics. For instance, there are algorithms that can find so-
lutions to the traveling salesman problem that are within 2 percent of the
best solution, and do so in a reasonable period of time. However, approxi-
mate solutions for one problem are not readily transformable into approxi-
mate solutions for another problem—for example, the decreasing-times
algorithm for the scheduling problem is generally only within 30 percent
of the best solution. The fact that the problems that Cook showed to be
equivalent appear to require separate approximate solutions is part of the
charm—and frustration—of mathematical research. Maybe the next great
result in this area is an algorithm for transforming approximation tech-
niques for one of Cook’s tough cookies into approximation techniques for
the others such that the transformed approximation is within the same
percentage of the best solution as the original approximation.
NOTES
- COMAP, For All Practical Purposes (New York: W. H. Freeman & Co., 1988). As I’ve
already remarked, I think this is a terrific book; ideal for people who like math-
ematics, and pretty good for people who can’t stand it but have to take a course
in it. Estimation is an extremely important part of mathematics. These are ex-
amples of worst-case estimates. Worst-case estimating is also valuable because it
often highlights precisely which situations result in the worst case, which can
lead to better algorithms. - http:// mathworld .wolfram .com/ search/ ?query greedyalgorithm & x0 & y 0.
- A. K. Dewdney, Beyond Reason (Hoboken, N.J.: John Wiley & Sons, 2004). Dewd-
ney shows how to transform the satisfiability problem into the vertex cover prob-
lem (a problem in graph theory) by showing how to transform logical expressions
into graphs. I don’t think this is a general template for transformational tech-
niques. My impression is that there are a bunch of hubs, serving the same func-
tion for this area of mathematics that hub airports do for air travel; to show that
problem A is transformable into problem B, one transforms problem A to a hub
problem, and then the hub problem into problem B. - h t t p : / / w w w. m a t h. o h i o - s t a t e. e d u / ~ f r i e d m a n / p d f / P - P 1 0 2 9 0 5 1 2 p t. p d f.
168 How Math Explains the World