Last Tech Tuesday, we looked at complexity classes which group problems by their intrinsic difficult. There we encountered one of the great unsolved questions of Computer Science. Is P = NP? The class P is easy to define. It is the set of all problems that can be solved by a Turing machine in polynomial time, i.e O(n^k) for some k. So you might think that NP stands for non-polynomial time but you’d be wrong. Instead the class NP has the  same definition as P except for a non-deterministic Turing machine.

You may recall from the posts on Turing machines that for each state of the machine and symbol on the tape there is exactly one action to be taken (which results in a new state and possibly a symbol written to the tape and/or movement of the tape head). In a non-deterministic Turing machine there are multiple possible actions and the machine is assumed to be taking each of them simultaneously!

Now it is easy to see why such a machine could be very fast. Take the example that we used to motivate the study of complexity: guessing a string drawn from the letters A, G, C, T. We saw that at length 40 this would take 400,000 years for my MacBook. But a non-deterministic Turing machine could do it very quickly because it can essentially guess A, G, C, T simultaneously for each position. The running time for this machine would be O(n) for n being the number of letters in the string.

But wait, when I had introduced Turing machines I had made the claim that they are the most powerful model of computation. This non-deterministic Turing machine sure sounds more powerful. Yet, there is nothing that a non-deterministic Turing machine can compute that cannot also be computed by a normal one. How do we know that? Because we have a proof that shows that a non-deterministic Turing machine can always be simulated by a (normal) Turing machine.

Now my description of using a non-deterministic Turing machine already contained the seed for a different definition of the class NP. It is also happens to be the class of problems where we can verify a positive result in polynomial time. Consider the following problem. Given a set of integers, e.g. {-17, 2, 3, 12, -5, 21} is there a subset that adds up to 0? To answer this question an algorithm might proceed as follows: while there are subsets left, pick a subset and test if that subset adds up to zero and if it does report “yes”  – if we exhaust all subsets report “no”. Now for a set with n integers in it, there happen to be 2^n subsets, so our loop might run for a very long time as n gets large.

If we focus on just the verification bit for a moment though, it is trivial. To verify if a subset adds up to zero, all we need to do is add up the numbers in that subset. The biggest possible subset has n elements (the set itself) and we clearly see that the verification step is linear in n, i.e. O(n). We call a subset that adds up to 0 a proof or witness because it shows that the answer to the question is yes. We see here a fundamental asymmetry. In order to answer yes, all I need to do is supply a single witness. To answer no, I need to show that no such witness exists!

We also see how this maps nicely to our distinction between normal and non-deterministic Turing machines. The normal one needs to crank through our code as outlined above. The non-deterministic one gets to work on all the subsets simultaneously. A great many problems have this structure. For instance, if give you an integer n and a second smaller integer f you can easily verify if f is a factor of n. But if n is large there a many candidate numbers. On DuckDuckGo you can see a long list of such problems.

So now back to our original question. Is P = NP? Based on everything we have just discussed it would intuitively appear that NP should contain at least some harder problems that are not in P. That is how the complexity class diagram from last week is drawn. But we don’t know that with certainty. To date there is no proof and some people doubt there will ever be one. In the absence of a proof there is some possibility that for every problem in NP we eventually find an algorithm that executes in polynomial time on a normal Turing machine.

This turns out to be a question of potentially great practical implications, especially in the area of cryptography. Public key cryptography relies on the asymmetry in which it is easy to verify that a message was encrypted (or signed) using someone’s private key when you have their public key. But all of that would be meaningless if you can easily derive someone’s private key from their public one (this happens to be related to the factor problem I mentioned above). Ditto for bitcoin. Finding a number to complete a block is hard. Verifying (by hashing) that the number does complete the block is easy. Again, it is hard to overstate just how many problems fall into this category.