Euler, Hamilton, and $1,000,000

Seven frustrating bridges. Image: Bogdan Giuşcă, via Wikimedia Commons.

The modern city of Kaliningrad, Russia once had 7 bridges spanning 4 islands.  Back when it still had its famous 7 bridges, the city was called Königsberg.  Because of the unique configuration of the bridges, the question was posed: Is it possible to travel across every bridge exactly once?  The answer was no.  This problem was studied by Euler, and in honor of his solution is called the Euler path problem.  He broke down the problem to a graph, or a system of nodes connected by edges.  He proved that in order for a path that traverses every edge once to exist, only 0 or 2 nodes can have an odd number of edges leading to it.  His solution is elegant and makes solving problems such as the Königsberg bridge problem very easy.

William Rowan Hamilton, however, struggled with a more difficult problem.  Rather than using every edge exactly once, he posed the problem of visiting every node exactly once.  While this is easy for small graphs, it is very difficult to determine if an arbitrary graph (of, say, 1000s of nodes) has a route that visits every node exactly once.  At this point, with over 1000 nodes, we have exited the realm of human feasibility.  We could make the assumption that it would be easy to solve this with a computer, but that assumption would be false.  As it turns out, there is no known algorithm that efficiently solves this problem.

To make matters worse, the problem can be checked really easily.  It is almost trivial for a computer to determine that a Hamiltonian path is valid.  This brings us to an infuriating question: Because a problem can be checked easily, shouldn’t it be just as easy to solve?  Unfortunately, the answer is still unknown.  This is called P vs. NP and is one of the most important questions of the entire field of Computer Science.  In fact, it is such an important question that the Clay Institute of Mathematics selected it as one of their 7 Millennial Prize Problems.  Only 1 of these problems has been solved so far, despite each solution coming with a prize of $1,000,000.  While it is generally believed that P =/ NP, it has not been conclusively proven impossible.

The Hamiltonian path problem is part of a set of problems called NP-Complete.  This means that while it is easy to check the solution of any of these problems, it is nigh-impossible to come up with a solution.  Other problems in this category are equally famous and include the Knapsack problem, the Traveling Salesman problem (which is basically the Hamiltonian path problem made more difficult), and the Boolean Satisfiability problem.  Other, more obscure problems also belong category, such as: “Does an arbitrary Minesweeper puzzle have a solution?” or “Is it possible to travel between two given points in a randomly generated Pokemon map?” or “Does an arbitrary Legend of Zelda block-pushing puzzle have a solution?”  Each of these problems can be reduced to an existing NP-Complete problem, and to make matters worse, every NP-Complete problem can be reduced to any other NP-Complete problem.

If a positive solution to the P vs NP problem was found (so that P=NP), the implications would be staggering.  First, every NP-complete problem would be solvable in polynomial time.  Difficult algorithms, from complicated graphics meshing to image processing, would be made easy.  Almost every cryptographic system would be breakable quickly, including AES, the gold standard of symmetric cryptography.  This would have implications outside of the realm of computer science – for example, RNA protein folding is also NP-Complete.  With a new, super-efficient algorithm, the flu, hepatitis C, and every other RNA-based disease could be completely eradicated.  Huge strides could be made in the field of genetics, particularly in the manufacture of human proteins and enzymes.

If a negative solution to the P vs NP problem was found, the upside is that someone gets a million dollars.  That’s probably the best thing that will happen.  Suddenly, we will no longer have the hope of efficient algorithms.  We can settle for less-than-perfect algorithms and focus on more productive areas of research.  At the very least, the field of computer science will be able to say that they have answered one of the most difficult problems the entire area of study has ever dealt with.

Sources (for further reading): (NP-Hardness of Nintendo games)