Newsgroups: sci.math
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 19 Feb 91 20:40:39 GMT
Subject: Re: natural mathematics

m...@hubcap.clemson.edu (m j saltzman) writes:

>One possible way to think about nature "doing" math is the notion of
>an analog computer.  There are a number of such devices; two examples
>come immediately to mind:

> 2) Approximating the minimum-length Steiner tree connecting
> points in a 2-dim plane using soap film.  Place vertical
> pins in a board at the chosen points.  Dip the board in
> soapy water, and the film that forms between the pins will
> (with a little luck) be a good approximation to the shortest
> network connecting all the points, if addition of new
> junction points is permitted (again, in roughly constant time).
> Finding the true optimum is NP-hard on a digital computer,
> and any heuristic will be at least linear in the number of points.

It's important to realize that finding the optimum Steiner tree
consists of two parts: Choosing a topology for the tree and minimizing
the length of the tree for that topology.  The first part is the
NP-hard part, in the sense that proofs of the NP-hardness use certain
kinds of very regular Steiner trees for which the minimum length is
immediate from the topology.  The second part can be done quite
quickly, perhaps in time linear in the input size.

The soap-film computer chooses the topology at random, and quickly
finds the optimum Steinter tree for that topology.  Thus it is solving
only the easy part of the problem, doing it very quickly.  But if you
use as many CPUs as you have points--essentially putting a CPU in each
pin--you might be able to do as well as the soap-film computer.
Perhaps a better analogy would be to use a CPU for each soap molecule.

The situation is somewhat like the somewhat counterintuitive result
that SUBGRAPH ISOMORPHISM is NP-hard, but GRAPH ISOMORPHISM may not
be.  The situation is explained when you look at the SI proof and
notice that the graph for which we are seeking an isomorphic subgraph
is a clique, for which the GI problem is trivial.  So all of the
difficulty in SI is accounted for in choosing the subgraph; the
isomorphism part may as well be thrown in for free.

Dan