advertise
« Stuff The Internet Says On Scalability For June 15, 2012 | Main | Monday Fun: Seven Databases in Song »
Wednesday
Jun132012

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

Reader Comments (2)

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

June 13, 2012 | Unregistered CommenterPas

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.

June 18, 2012 | Unregistered CommenterPies

PostPost a New Comment

Enter your information below to add a new comment.
Author Email (optional):
Author URL (optional):
Post:
 
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>