**NP-Hard Problems**

In Software there is a set of Problems called NP-Hard problems. I think my audience would run screaming if I explained this in technical detail (either they already know it and would be bored or would find it boring in general). I'll give two examples though:

- Subset Sum: Given a list of N integers, determine whether or not any non-empty subset of these integers sums up to zero (or any other number).
- Traveling Salesman: Given a map of the world and a list of N cities find the shortest path for a traveling salesman to visit all of these cities.

The story as I understand it (and I may have this off) was that there were a bunch of really smart algorithms folks working on problems like these two over at Bell Labs(?) back in "the day". They were trying to find algorithms for solving these problems. The problem is that the only algorithms they could come up with took exponential time to solve as N grew. So, if they could solve the traveling salesman problem with 3 cities in 1 second, it might take 2 seconds to solve with 4 cities, 4 seconds to solve with 5 cities, 8 seconds with 6 citites and so on. By the time you hit 30 cities it takes you over 4 years to solve the problem. Well before you hit 1,000 cities no computer known to man can solve the problem before the sun explodes.

Thats a problem. It's also embarrasing if it is your problem and you can't solve it. Some folks tried the reverse approach. After getting tired of trying to find a faster solution, they tried to prove that there was no faster solution. This is a common approach for this kind of problem, it is good to know that you aren't stupid and you can prove it. Unfortunately they couldn't prove that there wasn't a faster solution either.

So, all of these smart folks started talking to each other. Someone then figured out that their problem was actually equivalent to someone else's - that is if you could solve one you could solve the other. They started asking around and determined that there were many of these problems and that in fact they were all working on the exact same problem, described in different ways. For example, the two problems I stated above, the Subset Sum problem and the Traveling Salesman problem, are the same exact problem.

**Life is NP-Hard**

Other than being mathematically the same problem, I see that most NP-Hard problems have some common characterstics:

- There are partial solution, such as
path between all of the citites which may not be__a__path.__the__ - If you have two partial solutions, you can somewhat easily compare them and determine which one is better.

Many things in life have similar properties: If I look back at my life 1 year ago I can evaluate several things about my life now and my life then and directly compare them. Wealth is one thing, happiness (to a point) is another that I can do this with. The only problem is that I can't evaluate what the best possible state could have been today - what would have happened if I did X in the last year instead of the Y that I did. So, in a sense it is NP-Hard because the number of possible combinations of things in my life make it impossible for me to predict which combination will be the best, but I am somewhat (not completely) able to predict the outcome of a few different options. If I choose to go spend $100k on a new car, I have a good idea of how much that choice will affect my financially and a good idea of how much it will affect me in happiness. I don't know exactly, but I have a good idea (hence I don't buy said overpriced car).

Another example is the economy. I am not making a political statement, although it might sound a little like that right now. An economy is a state that can be directly evaluated and compared (the GDP of is $X today and $Y tomorrow), but the complexity of the state that made the economy the way it is makes it impossible to guarantee that it couldn't have been better (or worse). However, one can with some reasonable accuracy make some predictions about the path. For example, one might predict that lowering the Federal Interest rate will improve the economy and if that person was an expert, they could have high confidence in the effect of the choice.

OK, so I can't prove that the economy is mathematically equivalent to the traveling salesmen problem. I can't even prove that the sum subset problem is equivalent to traveling salesman. Still, I have a suspicion that they are equivalent or at least close

**Solving NP-Hard Problems in Polynomial Time**

Back to Software for a moment. It turns out that there is a common strategy for solving these NP-Hard problems. The strategy doesn't guarantee that you will find the best anwer, or even that you will find a good answer. But it guarantees to try and in practice usually it works very well. The strategy has a few different names, but a common name that is pretty layperson descriptive is "hill climbing". I'm going to steal some of the graphics from that wikipedia article and modify them, because I'm lazy and drawing 3d objects by mouse is kinda hard, so I'd better reference wikipedia.

Here is my best attempt at a non-technical explanation of hill climbing. Its actually pretty easy, so don't run away. Imagine you have one goal in life: namely to get as high (altitude not narcotic) as possible. Flying is out and to make things hard you are blind. But you do have a perfect GPS device that you can press a button on and it will tell you the exact height of the point you are standing on now.How would you try to get high? The simplest answer is hill climbing. Imagine that this image on the right (image here) is your world. You start out somewhere on this world. You take a step in any direction and see if you have gotten higher or not. If not, you step back and try a new direction. If so, you repeat the process. So, with every step you get progressively a little bit higher. If this image is your world, you would eventually get to the top, and it wouldn't take all that long either. That is hill climbing, and it solves NP-Hard Problems in Polynomial time. With travelling salesman, for another example, you would start with a random path through all cities, then try swapping the order of two cities in your original path. If the change gives you a shorter path, keep it, otherwise reverse it and try something else. It works pretty well.

The problem with hill climbing is that it doesn't always work perfectly. Imagine if instead our blind friend lived in the world on the left. There are two hills here, one being higher than the other. If our blind friend were to start climbing the left hill, he may very well get to the top of it, declare himself the highest man in the world since he can't climb any further, and he might be very wrong. How sad. This phenomenon in hill climbing is called "local maxima".

These "hills" are present in any problem. The height of the hill is it's utility: time to travel to all cities, wealth, etc. The x, y location are the parameters required to achieve that utility, although it is often far more than 2 dimensions that are at play.

The reason it works is that things are rarely completely random. Most of the time small changes in a situation have small effects on your utility function and large changes have large affects. Whether I choose to eat an apple or a banana has little affect on my happiness, but whether I choose to eat ice cream every day for the next month or excercise every day for the next month could have a large affect. The problem with large changes is that the larger they are, the less I can tell in advance what the outcome will be (remember, I'm blind on this hill). The ice cream tonight is stepping uphill - I know it will make me happier right now. Excercise is stepping downhill - I know it will cause pain and make me less happy right now, but it might be stepping downhill for the sake of eventually stepping up onto a much higher hill. On the other hand, it might not be because the downhill part is so long that I'll give up and walk back up my shorter hill by eating ice cream again.

Economics are another interesting example. A free economy, Adam Smith's laws of supply and demand, are a great way to allow hill climbing to work. If there is more demand for bread than apples, the price of bread increases until farmers decide to plant more wheat and less apples to increase their farm's revenue. The system prevents itself from going overboard - if the farmer produces too much wheat, it will suddenly become more valuable for him to produce more apples. Eventually the hill will be climbed when the perfect balance between apples and wheat is reached - and nobody needs to know what that balance is in advance (the "invisible hand" of economics). The problem with this is that there are local maxima at play in an economy. What if instead of growing wheat, the farmer could start researching a new apple that tasted twice as good. For many years, the farmer may be losing money (walking downhill) on this research until that better apple began to materialize. The longer the downhill stint, the harder it will be to get to a new hill. What if there exists a cheap way of producing limitless clean energy without coal or oil, but it takes billions of dollars of research money and a decade of research to discover it. Adam Smith would be hard pressed to get us there.

**Self Help**

So, now I'm given a mathematical basis for self-help material, yay. Climb Hills, but occassionally look for new ones. Makes alot of sense, but I find it comforting and useful to think of the world in this way.

PS: If you know the difference between NP-Hard and NP-Complete and caught me mixing them somewhere in there, don't complain in the comments, send me your resume, Google is interested. My rot13'ed email address is ttebgunh@tznvy.pbz .

**Edit (10/21/2009):**

An astute reader pointed out that I did indeed confuse NP-hard and NP-complete, and actually abused the whole notion altogether. Technically, the TSP problem is I stated is not a classical example, not exactly. Classically, NP-hard/complete problems are those with binary decisions as output. So, we aren't usually finding the shortest traveling path, we are answering the question of if the shortest path is less than distance X. That said, if you could tell me what the shortest path is, I could trivially tell you if it is less than X.

The class of problems that can be reduced into different versions of each other are NP-complete, whereas NP-hard simply means that it is at least as hard as NP-complete. This produces a small problem with respect to the blog post. I really wanted to talk about problems that could be transformed into each other, and problems where you want to optimize, not just determine if an optimization was possible. The first is NP-Complete, but "Life is NP-Complete" just lacks the same ring as "Life is NP-hard".

## 5 comments:

Lucid and enlightening. But what exactly do n and p stand for? the variables?

I like your post, specially the title :-) Thanks for sharing.

Btw Anupam, NP means Not Polynomial.

Cheers,

Carl.

NP means Non-deterministic Polynomial-time

I got here googling 'life is NP-hard', hoping someone's made a T-shirt of it. :) But your argument isn't quite foolproof of course, and I'm thinking a stronger one could be made.

First off, yes, you mixed NP-complete and NP-hard, but your proof would have come out easier if you hadn't. NP-Hard problems are any which are as hard as or harder than an NP problem. So life is NP-Hard as long as it contains any NP-Complete problems as a subset. The very fact that NP-Complete problems exist and some people want to solve them trivially makes life NP-Hard (for those people).

Now, a more interesting proof stems from understanding that there are thousands of problems which are NP-complete, and some of them are just idealized versions of everyday activities. Whenever we try to pack a box efficiently we are making an approximate solution to an NP-complete problem. When we try to plan an efficient route to our various destinations we are of course solving a mini tsp, which I'd say is a good metaphor for what everyone tries to do every day-plan an efficient route through the goals of the day.

Interestingly, NP problems are usually studied as decision problems, which in effect ask 'is it possible? If so how?' so any time we ask ourselves that question, and the answer can be checked for sanity in polynomial (usually linear or something akin to nlogn) time, we are doing something NP-hard.

To prove life NP-hard, of course, it would definitely have to be stated as a formal problem, meaning an input-output situation, which I'd say life isn't really as a whole. Furthermore to be NP-hard something has to be verifiable in P, and though significant subsets of life are, I doubt we can really check whether a life was well-lived in polynomial time. A life is like a program unleashed upon the world, and a life well-lived never halts. We can never know sometimes whether a program will halt; the halting problem is not verifiable in P or in exponential time or in any finite function of input size.

I guess I'll email you, assuming you were serious.

Interesting. It would have been better if we could identity life problems we encounter whether it is a problem in P, NP, is it NP-hard or NP-complete, or a problem that is BQP or BPP?

By what is commented recently, is it a preposition that we are a living algorithm? A living Turing machine?

Post a Comment