Life is NP-Hard

I think that this is going to be one of my more interesting blog posts. It is philosophical in nature though and a bit long, so maybe it's boring, I don't know. Let me know in the comments if you like it or hate it. Lets get to it shall we?

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:

1. 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).
2. 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:

1. There are partial solution, such as a path between all of the citites which may not be the path.
2. 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 .