Success is in NP

One of the most interesting parts of theoretical computer science is complexity theory. At its core complexity theory attempts to answer this question: what kinds of problems are easy and what kinds of problems are hard for a computer to solve? Problems are divided up into two classes: P and NP.*

A problem in P is easy for a computer to solve. A problem in NP is (we think) hard for a computer to solve. However, all problems in NP share the same thing: if you have the right answer, it’s very easy for a computer to verify that the answer is right. 

So NP problems are problems where coming to the right solution is hard, but verifying that your solution is correct is easy. To me this sounds like success.

Now let’s dive into the details so that I can explain why I think this is true.

We said before that a problem in P is easy for a computer to solve. What this really means is that a problem in P is polynomial-time solvable. Basically we’re saying that if the problem is in P it can be solved in a reasonable amount of time by a computer. Something like calculating the greatest common divisor between two numbers is in P.

More interesting is the set of problems in NP. Problems in NP are not known to be solvable in polynomial time by a deterministic machine. This is a fancy way of saying that there may be a way for a computer to solve problems in NP in a reasonable amount of time, but right now we don’t know of a way to do it. 

A good example of a problem in NP is the traveling salesman problem. Imagine we have a network of 20 towns. Some towns are connected by a road and some aren’t. The traveling salesman problem asks: is there a way to visit every town in the network only once and return to the original town that you started in.

Imagine Alan is a salesman trying to figure this problem out without a map. He knows the towns that are connected with roads to the town he is currently in, but he has no way of getting an overall picture of the problem. The only way to solve this is essentially by trying every single combination of routes from one town to another until he ends up back at the town he started in. As you can see, this will probably take Alan a while.

But here’s the interesting distinction. Let’s say you were Alan’s skeptical boss. It would be very easy to verify that Alan had indeed found a route that visits each city only once and ends up back at the town he started in.

Before he starts out on his journey Alan says, “Hey Boss I’m going out on my awesome sales route.”

All you have to do is give Alan a napkin and say, “I don’t believe you’ve found this route. To prove it here’s what I want you to do: every time you reach a city write the city’s name on this napkin.”

Alan’s an honorable guy; you know he wouldn’t cheat at this. And so he sets off on his journey. When he arrives back a few weeks later, all you have to do is look at the napkin with the list of cities he’s visited and compare it to the list of cities he should have visited. If every city is accounted for, you’ve verified that Alan has solved the problem.

I believe that success is very similar to this. Just like Alan has to visit every possible combination of cities in order to figure out how to go to each city only once and end up back at the city he started in, successful people have tried thousands of different combinations of actions to reach their goals. This takes years and years. It’s a hard problem.

But once they hit on the right combination of ingredients (specific to them and their particular situation) it’s very easy verify that such a combination did indeed make them successful. 

People say “In order to be successful Bill Gates did this, then this, then this, then this, and then Microsoft IPO’d.” But in reality what happened is Bill Gates tried millions of different combinations of actions and ideas (many of them simultaneously) but eventually he hit on a path that took him where he wanted to go. Then he showed us his napkin with the route he took, so that we could verify it.

I’m still figuring out what to write on my napkin. Are you? 

P.S An interesting extension of this concept is the VC firm. A VC firm is like giving Alan the traveling salesman superpowers. Imagine if every time Alan is in a town and needs to decide which town to go to next, he could split himself up. One copy of Alan goes to town A, one copy of Alan goes to town B, and one copy of Alan goes to town C. When those copies have to make decisions they just make more copies. The first copy to arrive at the town Alan originally started in has solved the problem.

If there are a bunch of copies of Alan running around from one town to another it makes it much easier to come to a solution. VC firms do this with companies. They have a bunch of companies running from town to town trying to solve “success.” Most of the companies get tired of doing all that running and die out. One or two find that route in a reasonable amount of time. We see them showing us their napkins in tech news every day. 

*Saying that problems are divided into P and NP is a simplification. P problems are in fact contained within the set of NP problems. However, all problems in NP may or may not be in P. 

I’d love to hear from on Twitter at @danshipper. Or check out my startup Airtime for Email. We help you standardize and centrally control all of your company email signatures.