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.

really beautiful blog entry!