NP-Completeness and Reduction: From Definitions to the 3-SAT to Vertex Cover Proof

Two definitions and one proof. The definitions are P and NP, and I am going to give them in terms of a machine that checks answers, rather than in terms of how hard a problem happens to feel. The proof is a single reduction, from three satisfiability to vertex cover. Gadgets drawn, wires connected, and both directions argued on one formula small enough to hold in your head. Start with a graph. Six places, and seven roads joining them. I want to post a guard at some of the places, so that every road has a guard at one end of it or the other. A set of vertices that touches every edge like that is called a vertex cover. Taking all six would certainly work, so the interesting question is never whether a cover exists. It is how small one can be. So we ask it as a question with a yes or a no attached. Given the graph and given a number k, is there a vertex cover with at most k vertices? For this graph, take k equal to three. Here is a claimed answer: the set containing b, and d, and f. In complexity that object has a name. It is a certificate, a piece of evidence offered alongside the instance to make the yes easy to confirm. Now check it. The size first. Three vertices, and three was the budget. Then the edges, one at a time, all the way round the outside and then across the middle. Every one of the seven has a lit endpoint. So the answer for this instance is yes, and the certificate is what proved it. Notice how little work that was. Seven checks, one per edge, and nothing had to be searched for. Finding the set is a different business entirely. There are twenty ways to choose three vertices out of six, and here you could try them all. Push the graph up to a hundred vertices with a budget of fifty, and that same brute force never finishes. That gap, between checking an answer and finding one, is the whole of what NP is about. So let us make it precise. A verifier for a problem is an algorithm V that takes two inputs. The instance w, which here is the graph together with the number, and the certificate c, which here is the proposed set of vertices. Three conditions on it. First, V runs in time polynomial in the length of w. Notice that this bounds the certificate too, since V cannot even read a string longer than the time it is allowed. Second, if w is a yes instance, then some certificate makes V accept. Third, if w is a no instance, then no certificate whatsoever makes V accept. Not a clever one, not a lucky one. None. NP is the class of problems that have a verifier like that. Now read the second line again and notice what it does not mention. It promises that a certificate exists. It says absolutely nothing about how you would find one. P is the same definition with the certificate deleted. A problem is in P when a polynomial-time algorithm decides it outright, working out the answer with no help offered. NP is the class we have just built. A polynomial-time verifier, and a short certificate for every yes instance. Every problem in P sits inside NP, because an algorithm that already knows the answer can simply ignore whatever certificate you hand it. Whether the containment runs the other way as well is the open question, and nobody knows. One last thing about the shape of that definition. It is lopsided, and on purpose. NP promises a short proof for the yes answers, and promises absolutely nothing for the no answers. Vertex cover shows you why. To demonstrate that a cover of size three exists, you point at one, like this. To demonstrate that none exists, you would have to rule out every subset, and there is no short way to write that down. So that is the class. Now the question that organises everything else. What does it mean to say that one problem inside it is harder than another?

Suppose I have two problems, A and B, and suppose somebody has already handed me a solver for B. Can I get A for free? Sometimes I can, and this is the shape of the arrangement. Take any instance w of A. Run it through a translator, a function f, and out comes a string. Hand that string to the solver for B, and take whatever the solver says as your answer about w. For that to be honest, f has to be faithful. w is a yes instance of A exactly when f of w is a yes instance of B. Not usually, not most of the time. Exactly when, and in both directions. And f itself has to be cheap: computable in polynomial time. If translating cost more than solving, the whole arrangement would be pointless. A translator with those two properties is a polynomial-time reduction, and we write it with this symbol. Read the symbol as no harder than. A is no harder than B, up to a polynomial. Now read that picture as a claim about difficulty, because this is where people get turned around. Suppose B has a polynomial-time algorithm. Then A has one too. Translate, then solve, and both steps are polynomial. Turn that implication around and you get the useful form. If A has no polynomial-time algorithm, then B cannot have one either, because a fast B would have handed us a fast A. So hardness travels forwards along the arrow, out of A and into B, while easiness travels backwards. Point at the arrow and you are pointing at the direction of the claim. That single sentence is most of what an examiner is checking. Which fixes the direction you must write your proof in. If you want to show that your new problem B is hard, you take a problem already known to be hard, and you reduce it into B. The other way round does prove something, but not that. A reduction from B into three satisfiability says B is no harder than three satisfiability. That is an upper bound, not a lower one. It is the single most common way to write the proof backwards, so when you are stuck, ask which problem is the source of the arrow. The source is always the one you already trust to be hard. Now the two names. A problem B is NP-hard when every problem in NP reduces to it in polynomial time. Every one. Including all the ones nobody has thought of yet. And B is NP-complete when it is NP-hard and it is itself a member of NP. The NP-complete problems are the hardest problems in the class, and they all stand or fall together. That definition looks impossible to verify, because NP contains infinitely many problems. Cook and Levin did the impossible part once, in nineteen seventy one, by encoding an arbitrary polynomial-time verification directly as a Boolean formula. Three satisfiability, the restriction where every clause has exactly three literals, is NP-complete too. So nobody after them has to go back to Turing machines. You reduce three satisfiability into your problem, and transitivity carries all of NP along behind. Which is exactly what we are going to do now, once, in full.

Three satisfiability. You are handed a Boolean formula in one fixed shape. It is a conjunction of clauses, and each clause is a disjunction of exactly three literals, where a literal means a variable or the negation of one. The question is whether some assignment of true and false to the variables makes the whole formula come out true. And here is the formula we are going to carry for the rest of the lecture. Three variables and two clauses. The first clause is x one or x two or not x three. The second is not x one or not x two or x three. Small enough to settle by inspection, which is exactly why it is safe to use. We are not going to be clever about this formula. We are going to translate it, mechanically, into a graph and a number. The translator is built from two pieces, one for each kind of object a formula contains. First piece: one gadget for every variable. It is a single edge, and its two endpoints are the two literals of that variable. x on one side, not x on the other. A cover has to touch every edge of the graph, and this is an edge. So any cover at all contains at least one of these two vertices. That is a cost we are going to charge for in a moment. And here is the reading that makes the entire proof work. Which endpoint the cover takes is a truth value. Take the x side and we call x true. Take the not x side and we call x false. The gadget is a switch. Second piece: one gadget for every clause. It is a triangle, and its three vertices are the clause's three literals, one copy of each. A triangle has three edges, and no single vertex touches all three. Take just the top one: it meets two of the edges and misses the bottom edge entirely. So one vertex is never enough. Take any two of them and every edge is covered, whichever two you choose. So each triangle costs at least two vertices. Equivalently, exactly one of the three can be left outside the cover, and that fact is what the whole proof will lean on. Third piece, and this one is not a gadget but a wire. For every literal in every clause, join that clause vertex to the variable gadget vertex carrying the same literal. Here the triangle's x vertex is wired back to the x endpoint upstairs. The other two literals of this clause would run off to their own gadgets, which I have not drawn. That is the whole construction. Two vertices and one edge per variable, three vertices and three edges per clause, and one wire per literal. Nothing depends on anything being clever. And now the number. With n variables and m clauses, set k to n plus two m. One vertex per variable gadget, two per clause gadget, and not a single vertex to spare. That tightness is the engine of the whole proof. The gadgets force n, the triangles force two m, those vertex sets do not overlap, so every cover has at least that many. Asking for exactly that many leaves no freedom anywhere.

Here is our formula again, and here is the graph it becomes. Three variables, so three variable gadgets. One edge each, six vertices in all, one pair per variable. Two clauses, so two triangles. The first clause is x one or x two or not x three, and its triangle carries exactly those three literals, one vertex each. The second clause is not x one or not x two or x three, and its triangle carries those. Notice that every literal now appears twice over. Once up in a gadget, and once down in a triangle. Now the wires. Every clause vertex joins the gadget vertex with the same label. The x one copy runs up to x one, the x two copy runs to x two, and the not x three copy runs all the way across the picture. The second triangle wires the same way. Not x one, not x two, and x three, each to its own endpoint upstairs. Six literals, six wires. Twelve vertices and fifteen edges. Look at how that was built. One pass over the formula, writing down a fixed number of vertices and edges per variable and per clause. That is the polynomial-time half of the reduction, and it is the easy half. Now the number. Each of the three variable edges demands at least one vertex, because a cover has to touch it. Three edges, one apiece, so three. Each of the two triangles demands at least two, as we showed. Two triangles, two apiece, so four. And those five demands sit on completely separate vertices, so they simply add. Rule a line under them and add. Seven. Every vertex cover of this graph has at least seven vertices, whatever it looks like, and seven is exactly the budget the construction sets. So asking for a cover of size seven is asking for one with no slack at all. Exactly one endpoint from each variable edge. Exactly two vertices from each triangle. Nothing left over to patch anything up with. Take the formula's side first. Set x one true, x two false, and x three true. Check it against both clauses. Clause one is x one or x two or not x three. Its first literal is true, so the clause holds. Clause two is not x one or not x two or x three, and not x two is true, since x two is false. Both clauses hold, so the formula is satisfied. Now build the cover from that assignment. From each variable gadget, take the endpoint whose literal came out true. x one true, so take x one. x two false, so take not x two. x three true, so take x three. Three vertices so far. Now each triangle. Look at which of its literals the assignment made true, pick one of those, and leave that vertex out. Take the other two. In the first triangle, x one is true. So leave the x one copy outside, and take the x two copy and the not x three copy. In the second triangle, not x two is true. So leave the not x two copy outside, and take the other two. Two from each triangle, four in all, and three plus four is seven. Exactly the budget. Now the part that could actually fail. Is every edge of this graph covered? There are three families to check, and I will take them in order. The three variable edges. We took one endpoint of each of them by construction, so all three are covered, and there is nothing to argue. The six triangle edges. We took two of the three vertices of each triangle, and two vertices of a triangle meet all three of its edges. So all six are covered as well. The six wires are the interesting family. If a wire's clause end is in the cover, that wire is covered and there is nothing to prove. So the only wires at risk are the two hanging off the vertices we deliberately left out. And look where those two wires go. The excluded vertex in the first triangle is the copy of x one, and its wire runs up to the gadget vertex x one, which is in the cover, because the assignment made x one true. Same story in the second triangle. The excluded vertex is the copy of not x two, its wire runs up to not x two, and we took not x two into the cover precisely because x two is false. Both risky wires are covered. That is the forward direction complete. And notice exactly where satisfaction was used. The vertex we leave out of a triangle has to be a true literal, and true literals are precisely the ones the gadgets put into the cover. An unsatisfied clause would have nothing safe to leave out. Now run it backwards, which is the direction that actually carries the theorem. Somebody hands you a cover of size seven for this graph. They will not say where they got it, and it need not be the one we just built. The counting does the first job for us. Seven vertices, and we proved the minimum is seven, so there is no slack anywhere. Exactly one endpoint of each variable edge, and exactly two vertices of each triangle. So read the assignment straight off the top row. This cover took not x one, so x one is false. It took x two, so x two is true. It took not x three, so x three is false. Well defined, precisely because exactly one of each pair was taken. Does that assignment satisfy the formula? Here is the argument, and it takes three steps. In each triangle exactly one vertex is left out. In the first triangle, the excluded vertex is the copy of x two. That vertex has a wire running up to the gadget vertex x two. The wire is an edge, and every edge is covered. Its clause end is not in the cover, so its other end must be. The gadget vertex x two is in the cover. And a gadget vertex in the cover is a literal we are calling true. So x two is true, and x two is one of the three literals of this first triangle, which is clause one. Clause one is satisfied, and we never had to look at its other two literals. The second triangle goes the same way. The excluded vertex is the copy of not x one, its wire forces not x one into the cover, and not x one in the cover means x one is false. That literal belongs to clause two, so clause two is satisfied too. Both clauses satisfied, so the formula is satisfiable, and the assignment we read off the cover is the witness. Note what carried that argument. Not the cover's cleverness, but the fact that seven left it no room to be anything else.

So let us say precisely what we now have. A function that takes a three satisfiability formula and returns a graph together with a number, computable in time linear in the size of the formula. And a proof, in both directions, that the formula is satisfiable exactly when that graph has a vertex cover of size at most k. That is the definition of a polynomial-time reduction, met in full. Three satisfiability reduces to vertex cover. Now read that as a statement about vertex cover, which is what it is. Cook and Levin put satisfiability at the top, with every problem in NP reducing into it. Satisfiability reduces to three satisfiability, and our arrow carries the hardness one step further along. So vertex cover is NP-hard: every problem in NP reduces to it, by composing the arrows. And vertex cover is in NP, which we settled in the first few minutes. Hand me a set of vertices and I will check it against every edge in linear time. NP-hard and in NP: vertex cover is NP-complete. Now read the arrows once more, because the direction is the whole examinable content. The arrow runs from the problem already known to be hard into the new one, never the other way. What it says is a conditional. If you could solve vertex cover quickly, you could solve three satisfiability quickly, and therefore everything in NP quickly. It does not say the reverse, and it hands you no algorithm at all. Which brings us to the last point, and it is the one worth carrying out of the room. NP-hardness is not a proof that no fast algorithm exists. Nobody has proved that about any problem in NP, and nobody is close. What it is, is a ranking. Vertex cover sits at least as high as every problem in the class. So if you ever find a polynomial-time algorithm for it, you have not found an exception. You have proved P equals NP, and thousands of problems fall in the same instant. And that is exactly why the phrase describes the problem. The reduction is a construction on a page, checkable by anyone. It was true before you attempted the problem, it is true while you are stuck on it, and it will still be true long after P versus NP is settled. It says nothing whatsoever about you. It says where the problem stands.