Solving an NP-Hard problem with Soap

What’s the minimum length of road needed to connect n cities?
This combinatorics problem is NP-Hard (if you can find a polynomial time algorithm to solve it, then P=NP), and is therefore considered difficult to solve for a computer.
An awesome demonstration of the intersection of mathematics and physics – the tendency of soap bubbles to minimize their surface area ends up minimizing the appropriate distance and solving the problem.

Worth a watch:

Tagged , , , , , ,

One thought on “Solving an NP-Hard problem with Soap

  1. Nirav Desai says:

    really beautiful blog entry!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: