Why My Soap Film is Better than Your Hadoop Cluster

The ever amazing slime mold is not the only way to solve complex compute problems without performing calculations. There is another: soap film. Unfortunately for soap film it isn’t nearly as photogenic as slime mold, all we get are boring looking pictures, but the underlying idea is still fascinating and ten times less spooky.

As a quick introduction we’ll lean on Long Ouyang, who has really straightforward  explanation of how soap film works in Approaching P=NP: Can Soap Bubbles Solve The Steiner Tree Problem In Polynomial.

It’s computers, so playing the role of the motivating graph problem we have the Steiner tree problem, which Ouyang explains as:

Find the minimum spanning tree for a bunch of vertices, given that you can add additional points.

Soap helps solve this problem because:

• Soap, in water, acts a surfactant, which decreases the surface tension in water.
• This acts to minimize the surface energy of the liquid.
• This should minimize surface area (graph weight), and solve the problem.

Dip two glass plates, for example, with pegs between them into soap water, the soap would form a Steiner Tree around the pegs.

Here’s an example with 4 points from Valery Ochkov:


Jim Bergquist has several good soap film examples on his blog. He talks about the Steiner Tree Problem in Steiner Trees and Minimal Surfaces:

There is a physical analog to the Steiner Tree Problem that allows one to find the solutions without doing a single calculation. The soap films of a wire frame model will form a minimal surface. If one uses the positions of a set of parallel wires in the frame to represent the points and eliminates the unwanted surfaces of the bubbles produced by dipping the frame in a soap solution, a set of minimal surfaces will be formed which is analogous to the Steiner tree. The analogy is even better if one looks just at a plane perpendicular to the parallel wires.

Even more on Steiner Trees in Steiner trees and spanning trees in six-pin soap films.



We aren’t just limited to soap films, three-dimensional microfluidic networks can also be used to solve computationally hard problems. Here’s an example for the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in polynomial time.



Maybe one day we can use a REST API to hook our computers into a menagerie of slime mold, soap film, and fluidic networks. Now that’s a specialized cloud.

Related Articles

• Bubble Science Kit
• Soap Films Help to Solve Mathematical Problems
• Steiner trees and spanning trees in six-pin soap films
• Pentagon Soap Films
• "Minimal Surfaces" a Misnomer?
• Steiner Trees and Minimal Surfaces
• Design Challenge Results: “Evolution is Smarter than You Are”
• Soap Bubbles, Their Colours and the Forces which Mould Them
• Newtonian systems, bounded in space, time, mass and energy can compute all functions
• Using three-dimensional microfluidic networks for solving computationally hard problems (ppt)
• On Solving NP-complete Problems with Unconventional Models of Computation
• Focus: Soap Film Has Memory
• Getting there in much less time with a little soap or slime
• Approaching P=NP: Can Soap Bubbles Solve The Steiner Tree Problem In Polynomial Time? (ppt)
• The Use of Soap Film to Solve Torsion Problems?

Comments

[Pas]

Nature doesn't cheat, neither has it found the general solution for NP: http://www.youtube.com/watch?v=8bLXHvH9s1A&hd=1&t=28m00s :)

[Pies]

You do realize, that the soap bubble is not solving anything, because you still need the math to know the shape of the soap bubble? It's like saying you don't need to know how to calculate the time to get from A to B because you can go there.

[Artur Braun]

The soap bubble needs not be computed anymore. You see the minimal surface immediately. No calculation needed. the only thing what you need may be a mapping into some storage medium, either your eye, some paper or some other device. The "read out" is what remains to do. There may be systems where this read-out is easier done than doing the actual computation. It is so trivial that it is almost unbelievable, but we need no (further) math for knowing the shape of the bubble construct.

[Ben]

This article is wrong. Soap film analog computers find a locally optimal spanning tree by a simple hill climbing "algorithm". Digital computers can find local optima like this much more rapidly and accurately than soap-film computers. The hill climbing approach doesn't solve the Steiner tree problem except in simple cases where the local optimum happens to be the global optimum.

You might as well say that you can solve the travelling salesman problem by trying 100 random routes and picking the shortest one as your solution. That may be good enough for some applications, but it doesn't solve the TSP and it doesn't prove that P=NP.