Category: Grad School

Theoretical problems in computer science are divided into classes based on their complexity. One class, called simply “P,” covers all problems requiring a yes-or-no answer that can be answered in polynomial time–which is to say that the amount of time needed to solve the problem is the result of substituting its input size for the variable in a polynomial equation. This is an important distinction, because that usually means it can be solved by a given deterministic computer (regardless of its speed) in some reasonable amount of time (ie before the universe ends).

There’s another class of problems, called “NP,” that has a special relationship with P. If a problem is in NP, there is no known algorithm for it that produces a solution in polynomial time–but the problem of verifying any given solution to the NP problem is in P. So you can figure out whether an answer is correct relatively quickly, but determining what the answer is could take a very long time. Longer than the sun has left in its life, for example, or longer than the universe has been in existence so far.

A final set of problems, called “NP-Complete,” is a special subset of NP. NP-Complete problems are very general and powerful–so general, in fact, that any NP problem can be transformed into an instance of any NP-Complete problem (and the transformation algorithm produces results in polynomial time). As you might imagine, these problems are very hard to solve, but of course their verification problems are in P.

If anybody ever produces an algorithm that will solve an NP-Complete problem in polynomial time, it will mean that all NP and NP-Complete problems are also solvable in polynomial time. NP and P will be equivalent sets. This would be a huge breakthrough in theoretical computer science, and it is likely that it will never happen.

But nobody’s proven that any NP-Complete problem isn’t in P, either. We only know that NP-Complete problems are not in P yet. (There’s a standing bounty on this; proof either way will get you a cool million bucks.)

As with most things that seem pointlessly theoretical at first, it’s not hard to apply the P-NP distinction to real life. It’s often easy to figure out that you’ve received an obfuscated message of some kind, whether it’s encrypted or noisified or divorced from its context. It may even be easy, given a possible meaning for the message, to decide whether that meaning applies. But deciphering the message from scratch can be very, very hard.

The difference between knowing that something is a message and knowing what the message means produces the best small mysteries.