Field NotesP, NP, NP-hard, and NP-complete
The distinctions that are easy to mix up.
This is perhaps one of the biggest misconceptions among OIers.
You will often see remarks online such as "How do I solve this — isn't it an NP problem?" or "There's no choice but to search this one; it has already been proven to be an NP problem." Bear in mind that when most people say "NP problem" in such cases, they actually mean an NPC problem: they have not sorted out the concepts of NP and NP-complete. An NP problem is not the kind of problem that "can only be solved by search" — an NPC problem is. Well, that is that; the misconception has essentially been cleared up. Everything below explains what a P problem is, what an NP problem is, and what an NPC problem is, so you can stop reading if you are not particularly interested. You will then see how great an error it is to take NP problems for NPC problems.
Let me first say a few words about time complexity. Time complexity does not tell you how much time a program needs in order to solve a problem; it tells you how fast the required time grows as the problem grows. In other words, on a computer that processes data at high speed, how efficiently it handles one particular input says nothing about the quality of a program. What matters is what happens when that input grows by hundreds of times over: does the running time stay the same, does it slow down by hundreds of times as well, or by tens of thousands of times? If a program takes the same amount of time no matter how large the data, we say the program is good — it has O(1) time complexity, also called constant complexity. If the time grows in step with the size of the data, then the program's complexity is O(n), as with finding the maximum of n numbers. Bubble sort, insertion sort and the like, where doubling the data quadruples the time, are O(n^2). Then there are brute-force algorithms whose running time grows geometrically; these have O(a^n) exponential complexity, or even O(n!) factorial complexity. There is no such thing as an O(2*n^2) complexity, because the leading "2" is merely a coefficient and has no effect at all on how the program's time grows. Likewise, O (n^3+n^2) is simply O(n^3). So we would say that a program running in O(0.01*n^3) is less efficient than one running in O(100*n^2): even though the former wins while n is very small, the latter's time grows more slowly with the size of the data, and eventually O(n^3) far overtakes O(n^2). We also say that O(n^100) is smaller than O(1.01^n).
It is easy to see that the complexities above fall into two tiers, the latter always vastly exceeding the former no matter what: one tier is O(1), O(log(n)), O(n^a) and the like, which we call polynomial-level complexity, because the size n appears in the base; the other is the O(a^n) and O(n!) varieties, which are non-polynomial, and whose running times a computer often cannot afford. When we set out to solve a problem, the algorithm we choose normally needs to have polynomial-level complexity; non-polynomial complexity takes far too long and will usually time out, unless the data is extremely small.
Naturally, one is led to ask: can every problem be given a polynomial-time algorithm? Unfortunately, the answer is no. Some problems cannot admit a correct algorithm at all — these are called undecidable decision problems. The Halting Problem is a famous undecidable problem, and I have introduced and proved it in a dedicated post on my blog. Another example: output all permutations of the n numbers from 1 to n. No matter what method you use, your complexity is factorial, because you always need factorial time just to print out the results. One might say that such a "problem" is not a "proper" problem: a proper problem asks a program to solve something and output "YES" or "NO" (this is called a decision problem), or to output some optimal value (this is called an optimization problem). By that definition, I can still name a problem that is unlikely to have a polynomial-time algorithm: the Hamiltonian cycle problem. It goes like this: given a graph, can you find a path that visits every vertex once and exactly once (neither missing nor repeating any) and finally returns to its start (a path meeting this condition is called a Hamiltonian cycle)? No polynomial-time algorithm is known for this problem. In fact, this problem is precisely the NPC problem we shall discuss later.
Next, the concept of class P: if a problem admits an algorithm that solves it in polynomial time, then the problem belongs to P. P is the first letter of the English word "polynomial". Which problems are in P? NOI and NOIP rarely set problems that fall outside class P. Most of the olympiad informatics problems we commonly encounter are P problems. The reason is simple: a timing-out, non-polynomial program that merely brute-forces embodies no worthwhile algorithm.
Next comes the concept of NP. This one is a bit harder to understand, or rather, easy to misunderstand. Let me stress here (returning to the misconception I am so eager to dispel) that an NP problem is not a non-P problem. An NP problem is a problem whose solution can be verified in polynomial time. Another definition of NP: a problem whose solution can be guessed in polynomial time. Suppose my luck (RP) is excellent, so whenever a program needs to enumerate, every guess I make hits the mark. Now someone has been handed a shortest-path problem: is there a route from the start to the finish shorter than 100 units? They have drawn the graph from the data but cannot compute the answer, so they come to me: "How would you choose a path to travel the least distance?" I say, my luck is great, I can certainly point you at a very short path at random. So I scribble a few lines and say, take this one. The person adds up the weights along the path I indicated and — well, would you look at that — the path length is 98, under 100. So the answer emerges: a path shorter than 100 exists. When others ask how they solved it, they can say: because I found a solution under 100. In this problem, finding a solution is hard, but verifying one is easy. Verifying a solution takes only O(n) time — I can spend O(n) time summing up the lengths of the path I guessed. So, provided my luck is good and my guesses are accurate, I can always solve the problem in polynomial time. The plan I guess is always an optimal one, and no plan that fails to meet the requirements can trick me into picking it. That is an NP problem. There are of course problems that are not NP: you may have guessed a solution, but it does you no good, because you cannot verify it in polynomial time. The example I am about to give is a classic one; it points to a problem for which no way of verifying a solution in polynomial time is currently known. Clearly, the Hamiltonian cycle problem mentioned above is an NP problem, because checking whether a path visits every vertex exactly once is very easy. But let me flip the question around: does a given graph contain no Hamiltonian cycle? This version cannot be verified in polynomial time, because unless you have tried every path, you dare not assert that it "has no Hamiltonian cycle".
NP is defined for this reason: usually only NP problems can possibly have polynomial algorithms. We would not expect a problem that cannot even be verified in polynomial time to possess a polynomial-time algorithm for solving it. The reader will soon appreciate that the supposedly hardest problem in informatics — "the NP problem" — is in fact an inquiry into the relationship between NP problems and class P.
Clearly, every problem in P is also an NP problem. That is, if you can solve a problem in polynomial time, you can certainly verify a solution to it in polynomial time — once the correct answer is out, verifying any given candidate only takes a comparison. The crux is whether every NP problem is also a problem in P. We can put it again in set-theoretic terms: gather all the P problems into a set P, and put all the NP problems into another set NP, and obviously P is contained in NP. Today, all research on NP problems converges on a single question: does P = NP after all? The so-called "NP problem", in a nutshell, is one sentence: prove or disprove P = NP.
The NP problem has always stood at the summit of informatics. Summit, meaning it is highly eye-catching yet extremely hard to crack. In informatics research it is the ultimate unsolved
question, much like grand unification in physics or Goldbach's conjecture in mathematics.
So far this problem has remained beyond us — we simply cannot get a grip on it. Still, there is a general trend, a broad direction of travel. It is widely believed that P = NP does not hold; that is, most people believe that at least one NP problem exists for which no polynomial-time algorithm is possible. People are so convinced that P ≠ NP for a reason: in the course of studying NP problems they uncovered a very special class of NP problems called NP-complete problems — the so-called NPC problems. C is the first letter of the English word "complete". It is precisely the existence of NPC problems that convinces people that P ≠ NP. What follows will devote considerable space to NPC problems, and you will come to appreciate just how unbelievable NPC problems make P = NP.
To explain NPC problems, we first introduce a concept — reducibility (Reduction; some sources call it that instead).
Put simply, saying that problem A reduces to problem B means that a method for solving problem B can be used to solve problem A — in other words, problem A can be "turned into" problem B. Introduction to Algorithms gives this example. Suppose there are two problems: solving a linear equation in one unknown, and solving a quadratic equation in one unknown. We say the former reduces to the latter, meaning that if you know how to solve a quadratic equation, you can certainly solve a linear one. We can write two programs, one for each problem, and then find a "rule" by which we transform the input data of the linear-equation program into input for the quadratic-equation program, so that the two programs always produce the same result. The rule is: the corresponding coefficients of the two equations stay unchanged, and the quadratic coefficient of the quadratic equation is set to 0. Transforming the first problem into the second by this rule makes the two problems equivalent. Similarly, we can say that the Hamiltonian cycle problem reduces to the TSP (Travelling Salesman Problem): in the Hamiltonian cycle problem, let two connected vertices have distance 0, and let two vertices that are not directly connected have distance 1; the question then becomes whether a path of length 0 exists in the TSP. A Hamiltonian cycle exists if and only if a cycle of length 0 exists in the TSP.
"Problem A reduces to problem B" has an important intuitive meaning: the time complexity of B is higher than or equal to the time complexity of A. In other words, problem A is no harder than problem B. This is easy to understand. Since problem A can be solved using problem B, if the time complexity of B were even lower than that of A, then A's algorithm could be improved into B's algorithm, and the two complexities would end up the same. It is like solving a quadratic equation being harder than solving a linear one, because the method that solves the former can also solve the latter.
Clearly, reduction has an important property: reduction is transitive. If problem A reduces to problem B and problem B reduces to problem C, then problem A certainly reduces to problem C. The reasoning is elementary, so there is no need to elaborate.
With that in hand, the standard concept of reduction is easy to grasp: if one can find such a transformation rule that the input to any program A can be rewritten by that rule into input for program B, with the two programs producing the same output, then we say that problem A reduces to problem B.
Of course, by "reducible" we mean reducible in polynomial time (Polynomial-time Reducible) — that is, the method of transforming the input must be one that can be completed in polynomial time. A reduction is only meaningful if it can be carried out in polynomial time.
Good. From the definition of reduction we see that reducing one problem to another raises its time complexity while widening its range of applicability. By repeatedly reducing certain problems, we can keep replacing low-complexity algorithms that apply only to a very narrow class of problems with somewhat higher-complexity algorithms that apply much more broadly. Now recall what was said earlier about P and NP, bring in the transitivity of reduction, and naturally we want to ask: if we keep reducing upward, repeatedly finding a slightly more complex, larger NP problem that can "swallow" a whole family of small NP problems, might we eventually find a super NP problem with the highest possible time complexity that "swallows" every NP problem there is? The answer turns out to be yes. That is, such an NP problem exists, and every NP problem can be reduced to it. Put differently, once this problem is solved, every NP problem is solved. The existence of such a problem is hard to believe, and even more incredible: there is not just one of them — there are many; it is an entire class of problems. This class is the legendary NPC problems, the NP-complete problems. The emergence of NPC problems propelled the study of NP problems forward by leaps and bounds. We have good reason to believe that NPC problems are the most complex problems. Returning once more to the very beginning of this article, we can see that when people want to express that a problem has no efficient polynomial-time algorithm, they should say it "belongs to the NPC problems". At this point my purpose has finally been achieved: I have distinguished NP problems from NPC problems. By now this article has run to nearly 5,000 characters; I admire you for still reading it this far, and I admire myself for having written this far.
The definition of an NPC problem is very simple. A problem that satisfies both of the following conditions is an NPC problem: first, it must be an NP problem; second, every NP problem must be reducible to it. Proving that a problem is NPC is also simple. First prove that it is at least an NP problem, then prove that some known NPC problem reduces to it (by the transitivity of reduction, the second clause of the NPC definition is thereby satisfied; how the very first NPC problem came about will be introduced below). At that point you can declare it an NPC problem.
Since every NP problem can be reduced to an NPC problem, if a polynomial-time algorithm were found for any one NPC problem, then every NP problem could be solved by that algorithm, and NP would equal P. Finding a polynomial-time algorithm for an NPC problem would therefore be unbelievable. That is why I said earlier that "it is precisely the existence of NPC problems that convinces people P ≠ NP". We can understand this intuitively: NPC problems currently have no effective polynomial-time algorithm, and one can only search with exponential or even factorial complexity.
A word in passing about NP-hard problems. An NP-hard problem is one that satisfies the second clause of the NPC definition but need not satisfy the first (that is, the NP-hard class is broader than the NPC class). NP-hard problems are equally hard to solve in polynomial time, but they fall outside our scope of study, because they are not necessarily NP problems. Even if a polynomial-time algorithm were discovered for NPC problems, NP-hard problems might still be left without one. In fact, because NP-hardness relaxes the constraints, it may turn out to have higher time complexity than all NPC problems and thus be even harder to solve.
Do not imagine that NPC problems are empty talk. NPC problems do exist. There really is a very concrete problem that is an NPC problem. It is the one to be introduced next.
The next section introduces the logic circuit problem. This is the first NPC problem. All the other NPC problems are obtained by reducing this problem to them. The logic circuit problem is therefore the "progenitor" of the NPC class.
The logic circuit problem is this: given a logic circuit, does there exist an input that makes the output True?
What is a logic circuit? A logic circuit consists of several inputs, one output, a number of "logic gates", and a dense web of wires. Look at the following example and you will understand it at once, without any explanation.
┌───┐
│ In1├─→┐ ┌──┐
└───┘ └─→┤ │
│ or ├→─┐
┌───┐ ┌─→┤ │ │ ┌──┐
│ In2├─→┤ └──┘ └─→┤ │
&
nbsp;└───┘ │ ┌─→┤AND ├──→Output
└────────┘┌→┤ │
┌───┐ ┌──┐ │ └──┘
│ In3├─→┤ NOT├─→────┘
└───┘ └──┘
This is a fairly simple logic circuit: when Input 1, Input 2 and Input 3 are True, True, False or False, True, False respectively, the output is True.
Are there logic circuits whose output can never be True? Yes. The following is a simple example.
┌───┐
│In1 ├→─┐ ┌──┐
└───┘ └─→┤ │
│AND ├─→┐
┌─→┤ │ │
│ └──┘ │ ┌──┐
│ └→┤ │
┌───┐ │ │AND ├─→Output
│In2 ├→─┤ ┌──┐ ┌→┤ │
└───┘ └→┤NOT ├→──┘ └──┘
└──┘
In the logic circuit above, whatever the inputs are, the output is always False. We say that this logic circuit has no input that makes the output True.
Back to the point: given a logic circuit, does there exist an input that makes the output True — that is the logic circuit problem.
The logic circuit problem belongs to the NPC class. This has been rigorously proved. It clearly belongs to NP, and it can be proved directly that every NP problem reduces to it (do not assume that the infinitude of NP problems makes the proof insurmountable). The proof is quite complex; its gist is that the inputs and outputs of any NP problem can be converted into the inputs and outputs of a logic circuit (remember that inside a computer there is nothing but arithmetic on 0s and 1s), so for any NP problem, the task reduces to finding an input — that is, a feasible solution — that makes the result True.
Once the first NPC problem was in hand, a great many NPC problems followed, because proving a new NPC problem now only requires reducing a known NPC problem to it. Later, the Hamiltonian cycle became an NPC problem, and so did the TSP. A great many problems have since been proved to be NPC; if a polynomial-time algorithm were found for any one of them, all NP problems could be solved perfectly. Thus it is precisely because NPC problems exist that P = NP becomes incredible. There is much more of interest in the P = NP problem, waiting for everyone to explore further. Scaling this summit of informatics is the ultimate goal of our generation. What we need to do now, at the very least, is not to confuse the concepts.