Most everyone who has some interest in math or computer science has heard of the P vs. NP problem, and the concept of NP-completeness. Problem classes P, NP, and NP-complete are fundamental to the field of complexity theory, are there are many good introductions to them. This post is not going to be a good introduction; all I want to do is try to clarify some important details that are sometimes glossed over.
Details, details
In complexity theory, there are things that seem like they should be very important but, from this theoretical standpoint, turn out not to matter at all. Like the difference between n2 and n200. But sometimes a tiny detail makes all the difference. Even though I have some actual education on this topic, I’ll probably still get something subtly wrong. Complexity theory is a huge and very arcane field of research, and I only ever learned the basics.
I declare that P≠NP
A notorious unsolved problem in math is the question of whether the class P is (as seems very likely) a proper subset of class NP, or whether somehow P=NP.
I don’t want to start every sentence with “Assuming P≠NP…,” so from here on, I’ll assume that P≠NP. If, by the time you read this, it has been proven that P=NP, please disregard the rest of this post.
Problems and instances
A problem is a template, not a specific instance of a problem. For example, there’s a problem named PRIME NUMBER whose definition is “Given an integer N (≥2), is N prime?” An instance of that problem would be “Is 91 a prime number?”
We are only studying the type of problems known as decision problems: problems for which, for each instance, the answer is either YES or NO. An example of a problem that is not a decision problem is “Given a network of cities and roads, what’s the shortest route that visits all the cities?”. To make it a decision problem, you could change it to “… is there a route of length N or less that visits all the cities?”
Computers and Turing machines
We imagine solving a problem by writing a computer program that solves any given instance of it. The computer in this case is an abstract computer, something like a real computer, except that it has an unlimited amount of memory available. The exact design of the computer doesn’t really matter, provided it’s not deliberately obtuse. Oh, and it must be a classical computer, not a quantum computer — sometimes that makes a difference. For reasons of formality, such a computer is often called a “Turing machine”.
Size and time and space
In order to be relevant to the study of complexity classes, a problem generally must have instances of arbitrarily large size. A bounded problem like “Given a state of a standard Sudoku puzzle, does it have a solution?” would not qualify, because the number of such states is finite. Such a problem is solvable in constant time, so it is well inside class P. The constant might be ridiculously large, but that doesn’t matter. There are generalized variants of Sudoku that can grow to arbitrary size, but if that’s what you’re talking about, you really need to make that clear.
Unless specified otherwise, the size of a problem instance can be thought of as the number of characters it takes to write it down, using any sensible encoding scheme. The complexity class usually ends up being the same, for a wide variety of encoding schemes. If a problem instance definition contains numbers, it’s the number of digits in those numbers that counts toward the problem instance size, not the numbers themselves.
Most of the problems that are studied are defined in such a way that their definition uses only integers, and no other types of numbers. There’s no rule against non-integers, but you may have to clarify how they are to be encoded.
If a problem is solvable in “polynomial time,” it means the hardest problem instances of a given size can be solved in an amount of time that is bounded by some polynomial function of the size. For example, a polynomial function of S is S3. The exponent must be fixed, and not depend on the problem size.
In this post, I’m only looking at complexity classes defined by the amount of time it takes to solve a problem instance, not the amount of memory. There are many complexity classes that are defined by memory use (sometimes called “space”), just not the ones I’m discussing.
The basic complexity classes
Here’s a diagram of the relevant complexity classes:
- P is the class of decision problems for which all instances can be solved in polynomial time. (Here, “solved” means to produce the correct YES or NO answer.)
- NP is the class of decisions problems for which, for every instance whose answer is YES, there exists a proof-that-the-answer-is-YES that can be verified in polynomial time. It includes everything in classes P, NP-complete, and NPI.
- NP-complete is the class of the hardest problems in NP.
- NPI will be discussed later.
I’m just lumping everything else into “not NP” for now. “Not NP” includes problems that are strictly harder than NP, and problems that don’t meet the definition of NP for some other reason.
What is NP?
The definition of NP is one of those things that is almost easy to grasp, but not quite. And a lot of other things rely on it, so it’s worth making the effort to get it right.
There are many equivalent ways to define NP. I prefer the one I used above. For every instance whose answer is YES, a polynomial-time verifiable proof that the answer is YES must exist. It doesn’t matter how long it may take to find such a proof; it just must exist.
The key is that only the YES instances must have such a proof. Most definitions of NP have no explicit requirements at all about the NO instances (though, if I’ve got this right, the NO instances of any NP problem will necessarily be solvable, and in no worse than exponential time).
I defined PRIME NUMBER above. Now I’ll define COMPOSITE NUMBER: Given an integer N (≥2), is N composite?
You might think that PRIME NUMBER and COMPOSITE NUMBER are really the same problem. But they are, at least potentially, very different. That’s because of the asymmetry of YES and NO answers built into the definition of NP.
It’s simple to prove that COMPOSITE NUMBER is in NP. Any proper factor of N would constitute a proof of its compositeness. Verifying such a proof can be done by one act of long division, which is easy to do in polynomial time.
That’s not the case with PRIME NUMBER. Sure, if N is prime, you can prove it by doing trial division of all possible divisors. But that takes more than polynomial time, and it doesn’t lead us to a proof that can be verified in polynomial time. That gives us no reason to believe that PRIME NUMBER is in NP.
(In fact, PRIME NUMBER is in NP, as proven by Vaughan Pratt in 1975. Moreover, PRIME NUMBER and COMPOSITE NUMBER are in both P. That was only proven in 2002, via the AKS algorithm.)
A nondeterministic what-now?
NP stands for “nondeterministic polynomial.” It’s often defined as the class of problems that can be solved (in some particular way) by a “nondeterministic Turing machine” (or nondeterministic “computer”, or “algorithm”). Whatever that is.
Let’s not oversimplify it, though. It’s more like this:
- NP is the class of decisions problems for which a nondeterministic Turing machine can solve every instance whose answer is YES in polynomial time.
A nondeterministic computer is sort of like one that can execute an unlimited number of threads of computation in parallel. But there’s something critical that we still need to know: how to measure how much time it took.
The way I imagine it is that, for any thread that turned out not to contribute to the final answer, we can magically cause it to have never existed in the first place. So, the time it used does not count against us.
But all the threads that do contribute to the final answer must remain, and their times are added together. For a problem to be in NP, it’s this time that must be polynomially bounded.
What is NP-complete?
NP-complete is the set of the hardest problems in NP. This turns out to encompass a lot of interesting and important problems.
In many cases, proving that a problem is in NP is simple enough that you can do it in your head. That’s not the case for NP-complete. The only reasonable way to prove that a problem is NP-complete involves proving that some subset of it is isomorphic to some other problem that has already been proven to be NP-complete.
As a general guideline, though, an NP problem that can only be solved by something like a brute-force search is very likely to be NP-complete.
NP-complete is not a synonym for “hard” or “exponential”. (Solving an NP-complete problem does presumably require exponential time, but there are other exponential problems.) NP-complete problems are actually among the easiest problems outside of P, not the hardest. There are many harder problems, for which neither the YES nor NO instances have simple proofs, which typically happens when the space in which you have to search for a solution is unbounded.
And of course, you must never abbreviate NP-complete as “NP”. That’s just wrong. (Unless you have proven that they are equal. In which case, sure, go ahead.)
What’s with that NPI region?
Class NP is composed of three disjoint regions: P, NP-complete, and NPI. The I in NPI stands for “intermediate”.
NPI problems can’t be solved in polynomial time, but are easier than NP-complete problems.
NPI actually contains an infinite number of non-equivalent complexity classes.
There’s a small handful of interesting problems that are good candidates for being in NPI. But, as far as I know, not a single interesting problem has ever been proven to be in NPI. Only some highly artificial problems have been proven to be in NPI.
Entropymine 