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.
- 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?