P = NP

June 9, 2014

By your many years of attempting to impress your professors, you've learned the art of cocktail party conversation. Masters of this art will be able to talk grandly on most topics up to a limit of about a minute, at which time the conversation has hopefully changed subject. It's much more entertaining than just talking about the weather.

Things are a little harder when you're talking among your scientific peers, whose depth of knowledge transcends that of the typical Sangria sipper. In that case, you meed to haul out the big guns. Among computer people, a casual mention of the Entscheidungsproblem is usually all you need to gain your listener's respect without worrying about follow-up questions. It's a subject of which everyone has heard, because of its historical significance and association with Alan Turing, but very few have actually studied.

Since the early center of science and mathematics was Europe, including Germany, many fundamental problems have German names. These range from the simple Aufbauprinzip (Aufbau principle) to the tongue-twisting Entscheidungsproblem. This might be expected from a country where the research foundation is called Deutsche Forschungsgemeinschaft.

The "halting problem," as it's known in English, is a computer science version of the cinema scientist's lament that "there are things that Man was not meant to know." Possibly the best statement of the halting problem was written in 1935 by mathematician, Alonzo Church, who was considering what it means for a function to be calculable. He decided that the function would contain an algorithm, and you would know when the algorithm terminated; that is, the algorithm yields an answer.

In computer science terms, this means knowing that your program, for a particular input, will eventually halt, or goes on forever. Alan Turing, in his 1937 paper, "On Computable Numbers With an Application to the Entscheidungsproblem," addressed the problem by first constructing a universal computer, his Turing machine. He proved that it wasn't possible to decide whether a program on such a machine will halt, effectively proving that there are things that computer scientists are not meant to know.

A physical Turing machine, built by Mike Davey. You can see its operation in a YouTube video. (Photograph by "GabrielF," via Wikimedia Commons. Click for larger image.)

Deciding which problems are too hard to tackle is one task of an effective scientist. He might not know that his research will lead to a dead end, but the referees of his research proposal likely will. The halting problem notwithstanding, computers have been successfully performing many of our calculations for years. Despite these successes, there are some calculations that are very difficult.

One simple example of such a problem (simple enough to be presented in the cartoon shown below) is the subset sum problem. If you have a set of numbers, is it possible for members of the set to add to a particular number? There's no algorithm to do this; and, if you have many numbers in the set, you need to try a lot of combinations to see whether it's possible.

A cartoon from Randall Munroe's xkcd Comics, licensed under a Creative Commons Attribution-NonCommercial 2.5 License. (xkcd comic 287.)

The complexity of this calculation increases at a rate that's not known to be polynomial in time; that is, it's "nondeterministic polynomial" (NP) in time. Verification of the answer happens in polynomial time (P). A polynomial execution time for calculations involving N elements would be something like N¹, N², or N³, and so on. NP execution, however, would be something like 2^N, which becomes very large for large N.

It would be nice if every problem with a quickly verified solution would have an algorithm that allows its quick computation as well. In the language of computer science, we would like to have P=NP, rather than the converse, P≠NP. This P vs NP problem is an open problem that's important enough to have been designated one of the seven, million dollar, Millennium Prize Problems selected by the Clay Mathematics Institute. Its solution would be important to such diverse areas as cryptography and economics.

Public key cryptography involves the idea that it's easy to multiply two huge prime numbers to get an even larger number, but it's very difficult to factor that large number into its prime components. The factoring is NP. Nearly every NP problem is NP-complete, a terminology expressing the fact that a polynomial solution of any one of those can be easily applied to the rest.[1] The traveling-salesman problem, which I wrote about in a previous article (The Traveling Salesman Problem, March 1, 2013), is NP-complete.

The problem expressed in the above cartoon is NP-complete, but there are so few elements that the solution can be found by inspection, or just a few computer calculations. When the cartoonist, Randall Munroe, created the cartoon, he didn't realize that the problem had more than one solution.[2] These are seven mixed fruit orders and the combination of one order of mixed fruit, two orders of hot wings, and one sampler plate. One web site has a few elegant programs for the efficient solution of this particular problem.[3]

My computer solution is not at all elegant, although it is very general. I used a the Monte Carlo method, and you can view my C language source code, here. In the Monte Carlo method, you try random combinations of multiples of the items until you find one that works. There's some method to the madness, since you purposely don't select multiples of any one item that will go over the limit ($15.05, in this case), as shown in the table.

Item	Maximum Number
Mixed Fruit	7
French Fries	5
Side Salad	4
Hot Wings	4
Mozzarella Sticks	3
Sampler Plate	2

So, how well does this approach work? As can be seen in the histogram, the program often finds a solution after just a few random selections. If you just multiply the maximum numbers in the table, you get 3360, so you should expect to find a solution somewhat close to that number of random selections, if a solution exists. You'll note, also, that there are still cases for which a solution is found at our patience limit, which was 30,000 random selections.

Histogram of the number of random selections required to get a Monte Carlo solution to xkcd cartoon 287. 30,000 trials were attempted. (Gnumeric.)

References:

1. Larry Hardesty, "Explained: P vs. NP," MIT News Office, October 29, 2009.
2. Explain 287: NP-Complete, Explain xkcd Web Site.
3. Solving the NP-complete problem in XKCD, Stack Overflow Web Site.