P vs NP for Dummies

I seem to type up a variation of this post every few months. I'm saving this one for the permanent record.

P vs NP for Dummies

There are some yes/no problems which are easy. If I give you a list on numbers and ask you to tell me if the number 5 is in that list, you can solve it easily by looking at each number in the list. In the worst case, when the number 5 is at the very end of the list, this takes about n steps/instructions.

There are yes/no problems which are slightly harder -- for example, I might ask you to tell me if 12*14=168. When you multiply two n-digit numbers using the method you learnt in school, you need about n² steps.

Both of these problems require some number of steps that's bounded by a polynomial of the input size; i.e. for each of these problems there is a fixed k so that the number of steps required to solve an instance of that problem of size n it is always bounded by n^k . This class of problems is called P which is a terrible pseudo-abbreviation for 'polynomial time on a deterministic Turing machine' (a deterministic Turing machine is a standard computer, more or less).

Here's another yes/no problem: given a map of a country with n cities, determine whether there's a route that can be taken that visits every city exactly once, and whose total distance is less that a given distance d. If we are told that the answer is yes and we are given the corresponding route, we can easily check its total distance by simply following the route and adding up all the distances between cities. This verification process takes about n steps since you're adding n-1 numbers together. The set of yes/no problems whose solutions can be verified in polynomial time (given some extra information, in this case the route itself) is called NP. This specific problem is a special case called an NP-complete problem, meaning that it is in a sense 'harder' than all other problems in NP.

One might conjecture that, because you can verify a solution to this problem in a polynomial number of steps, then perhaps you can also solve it from scratch in polynomial time? Obviously all problems in P are also in NP, since if we can verify a solution to any problem in P in polynomial time by simply solving that problem and checking it against the given solution. Since this problem is 'harder' than all the other NP problems, if we can solve this one in polynomial time, then we can solve all the other NP problems in polynomial time too! This would mean that all NP problems are also P problems, in other words P = NP.

So you set out to try to find a polynomial time method to produce a solution to this problem. But you can't. No one can. We don't have a polynomial time method to solve for this problem. In fact we don't have a polynomial time method for any of the dozens of known NP-complete problems. These problems range from finding routes across maps, to packing items efficiently into a backpack, to optimally playing candy crush. On the flip side though, no one's managed to prove that a polynomial time method doesn't exist. Such a proof would demonstrate that P =/= NP.

So there you are. The problem of P vs NP is the problem of proving either that P=NP (this can be done simply by finding a polynomial time method to solve problem above) or that P =/= NP (this intuitively seems harder to prove).

For the route-finding problem described above (it's called the travelling salesman problem), the best currently known method is a small optimisation on "brute force every permutation of cities to visit". This method bound the number of steps by about n² * 2^n. If you can get rid of the exponential term in that expression, you get a million dollar prize and immediately render most of the field of cryptography obsolete.