### 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.

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.

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

^{1}, N

^{2}, or N

^{3}, 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:

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