WEBVTT 00:00:00.058 --> 00:00:02.416 Two definitions and one proof. 00:00:02.612 --> 00:00:07.198 The definitions are P and NP, and I am going to give them in terms of a machine 00:00:07.198 --> 00:00:11.994 that checks answers, rather than in terms of how hard a problem happens to feel. 00:00:12.790 --> 00:00:17.935 The proof is a single reduction, from three satisfiability to vertex cover. 00:00:18.131 --> 00:00:20.394 Gadgets drawn, wires connected, 00:00:20.477 --> 00:00:25.075 and both directions argued on one formula small enough to hold in your head. 00:00:26.890 --> 00:00:28.411 Start with a graph. 00:00:28.515 --> 00:00:31.546 Six places, and seven roads joining them. 00:00:31.743 --> 00:00:33.946 I want to post a guard at some of the places, 00:00:34.029 --> 00:00:37.130 so that every road has a guard at one end of it or the other. 00:00:37.741 --> 00:00:42.281 A set of vertices that touches every edge like that is called a vertex cover. 00:00:42.478 --> 00:00:44.334 Taking all six would certainly work, 00:00:44.417 --> 00:00:47.819 so the interesting question is never whether a cover exists. 00:00:48.016 --> 00:00:50.199 It is how small one can be. 00:00:50.903 --> 00:00:54.677 So we ask it as a question with a yes or a no attached. 00:00:55.129 --> 00:00:57.264 Given the graph and given a number k, 00:00:57.347 --> 00:01:00.703 is there a vertex cover with at most k vertices? 00:01:01.317 --> 00:01:04.464 For this graph, take k equal to three. 00:01:05.168 --> 00:01:09.717 Here is a claimed answer: the set containing b, and d, and f. 00:01:09.800 --> 00:01:12.645 In complexity that object has a name. 00:01:12.749 --> 00:01:14.059 It is a certificate, 00:01:14.142 --> 00:01:18.694 a piece of evidence offered alongside the instance to make the yes easy to confirm. 00:01:19.491 --> 00:01:21.985 Now check it. The size first. 00:01:22.068 --> 00:01:24.844 Three vertices, and three was the budget. 00:01:24.947 --> 00:01:25.863 Then the edges, 00:01:25.946 --> 00:01:30.196 one at a time, all the way round the outside and then across the middle. 00:01:30.992 --> 00:01:33.605 Every one of the seven has a lit endpoint. 00:01:33.709 --> 00:01:38.586 So the answer for this instance is yes, and the certificate is what proved it. 00:01:38.689 --> 00:01:40.908 Notice how little work that was. 00:01:41.104 --> 00:01:45.656 Seven checks, one per edge, and nothing had to be searched for. 00:01:46.871 --> 00:01:49.748 Finding the set is a different business entirely. 00:01:49.831 --> 00:01:52.953 There are twenty ways to choose three vertices out of six, 00:01:53.036 --> 00:01:54.648 and here you could try them all. 00:01:54.731 --> 00:01:57.911 Push the graph up to a hundred vertices with a budget of fifty, 00:01:57.994 --> 00:02:00.769 and that same brute force never finishes. 00:02:01.194 --> 00:02:03.955 That gap, between checking an answer and finding one, 00:02:04.038 --> 00:02:06.466 is the whole of what NP is about. 00:02:06.662 --> 00:02:08.648 So let us make it precise. 00:02:10.045 --> 00:02:14.434 A verifier for a problem is an algorithm V that takes two inputs. 00:02:14.538 --> 00:02:18.309 The instance w, which here is the graph together with the number, 00:02:18.392 --> 00:02:22.933 and the certificate c, which here is the proposed set of vertices. 00:02:23.730 --> 00:02:25.368 Three conditions on it. 00:02:25.564 --> 00:02:29.431 First, V runs in time polynomial in the length of w. 00:02:29.628 --> 00:02:32.110 Notice that this bounds the certificate too, 00:02:32.193 --> 00:02:36.072 since V cannot even read a string longer than the time it is allowed. 00:02:36.985 --> 00:02:42.767 Second, if w is a yes instance, then some certificate makes V accept. 00:02:42.952 --> 00:02:48.874 Third, if w is a no instance, then no certificate whatsoever makes V accept. 00:02:49.059 --> 00:02:51.684 Not a clever one, not a lucky one. 00:02:51.880 --> 00:02:52.752 None. 00:02:53.548 --> 00:02:57.810 NP is the class of problems that have a verifier like that. 00:02:57.903 --> 00:03:01.511 Now read the second line again and notice what it does not mention. 00:03:01.594 --> 00:03:04.402 It promises that a certificate exists. 00:03:04.485 --> 00:03:07.876 It says absolutely nothing about how you would find one. 00:03:08.901 --> 00:03:12.222 P is the same definition with the certificate deleted. 00:03:12.419 --> 00:03:17.225 A problem is in P when a polynomial-time algorithm decides it outright, working out 00:03:17.225 --> 00:03:19.386 the answer with no help offered. 00:03:20.182 --> 00:03:23.086 NP is the class we have just built. 00:03:23.282 --> 00:03:28.589 A polynomial-time verifier, and a short certificate for every yes instance. 00:03:29.386 --> 00:03:33.240 Every problem in P sits inside NP, because an algorithm 00:03:33.240 --> 00:03:37.885 that already knows the answer can simply ignore whatever certificate you hand it. 00:03:38.337 --> 00:03:42.051 Whether the containment runs the other way as well is the open question, 00:03:42.134 --> 00:03:43.783 and nobody knows. 00:03:44.580 --> 00:03:47.155 One last thing about the shape of that definition. 00:03:47.238 --> 00:03:49.782 It is lopsided, and on purpose. 00:03:50.234 --> 00:03:55.017 NP promises a short proof for the yes answers, and promises absolutely nothing 00:03:55.017 --> 00:03:56.504 for the no answers. 00:03:57.300 --> 00:03:59.681 Vertex cover shows you why. 00:03:59.785 --> 00:04:05.079 To demonstrate that a cover of size three exists, you point at one, like this. 00:04:05.276 --> 00:04:09.512 To demonstrate that none exists, you would have to rule out every subset, 00:04:09.595 --> 00:04:12.034 and there is no short way to write that down. 00:04:12.830 --> 00:04:14.688 So that is the class. 00:04:14.885 --> 00:04:17.426 Now the question that organises everything else. 00:04:17.509 --> 00:04:21.236 What does it mean to say that one problem inside it is harder than another? 00:04:22.295 --> 00:04:24.116 Suppose I have two problems, 00:04:24.199 --> 00:04:28.937 A and B, and suppose somebody has already handed me a solver for B. 00:04:29.389 --> 00:04:31.050 Can I get A for free? 00:04:31.502 --> 00:04:35.078 Sometimes I can, and this is the shape of the arrangement. 00:04:36.479 --> 00:04:38.999 Take any instance w of A. 00:04:39.103 --> 00:04:43.608 Run it through a translator, a function f, and out comes a string. 00:04:43.921 --> 00:04:46.137 Hand that string to the solver for B, 00:04:46.220 --> 00:04:50.017 and take whatever the solver says as your answer about w. 00:04:50.814 --> 00:04:53.784 For that to be honest, f has to be faithful. 00:04:53.867 --> 00:04:59.113 w is a yes instance of A exactly when f of w is a yes instance of B. 00:04:59.196 --> 00:05:01.542 Not usually, not most of the time. 00:05:01.738 --> 00:05:04.676 Exactly when, and in both directions. 00:05:05.473 --> 00:05:10.083 And f itself has to be cheap: computable in polynomial time. 00:05:10.280 --> 00:05:15.157 If translating cost more than solving, the whole arrangement would be pointless. 00:05:15.953 --> 00:05:19.388 A translator with those two properties is a polynomial-time reduction, 00:05:19.471 --> 00:05:21.364 and we write it with this symbol. 00:05:21.677 --> 00:05:27.843 Read the symbol as no harder than. A is no harder than B, up to a polynomial. 00:05:29.356 --> 00:05:31.817 Now read that picture as a claim about difficulty, 00:05:31.817 --> 00:05:34.314 because this is where people get turned around. 00:05:34.766 --> 00:05:38.017 Suppose B has a polynomial-time algorithm. 00:05:38.121 --> 00:05:39.991 Then A has one too. 00:05:40.443 --> 00:05:44.519 Translate, then solve, and both steps are polynomial. 00:05:45.222 --> 00:05:48.262 Turn that implication around and you get the useful form. 00:05:48.345 --> 00:05:50.956 If A has no polynomial-time algorithm, 00:05:51.039 --> 00:05:56.276 then B cannot have one either, because a fast B would have handed us a fast A. 00:05:56.979 --> 00:06:01.773 So hardness travels forwards along the arrow, out of A and into B, 00:06:01.856 --> 00:06:04.224 while easiness travels backwards. 00:06:04.421 --> 00:06:08.520 Point at the arrow and you are pointing at the direction of the claim. 00:06:08.717 --> 00:06:12.235 That single sentence is most of what an examiner is checking. 00:06:13.748 --> 00:06:17.023 Which fixes the direction you must write your proof in. 00:06:17.219 --> 00:06:19.864 If you want to show that your new problem B is hard, 00:06:19.947 --> 00:06:24.209 you take a problem already known to be hard, and you reduce it into B. 00:06:24.553 --> 00:06:27.433 The other way round does prove something, but not that. 00:06:27.629 --> 00:06:28.766 A reduction from B 00:06:28.849 --> 00:06:34.164 into three satisfiability says B is no harder than three satisfiability. 00:06:34.247 --> 00:06:37.034 That is an upper bound, not a lower one. 00:06:37.947 --> 00:06:41.068 It is the single most common way to write the proof backwards, 00:06:41.151 --> 00:06:45.482 so when you are stuck, ask which problem is the source of the arrow. 00:06:45.586 --> 00:06:48.826 The source is always the one you already trust to be hard. 00:06:50.130 --> 00:06:51.698 Now the two names. 00:06:51.894 --> 00:06:58.466 A problem B is NP-hard when every problem in NP reduces to it in polynomial time. 00:06:58.663 --> 00:06:59.825 Every one. 00:07:00.021 --> 00:07:02.855 Including all the ones nobody has thought of yet. 00:07:03.768 --> 00:07:09.875 And B is NP-complete when it is NP-hard and it is itself a member of NP. 00:07:10.327 --> 00:07:13.866 The NP-complete problems are the hardest problems in the class, 00:07:13.949 --> 00:07:16.562 and they all stand or fall together. 00:07:17.475 --> 00:07:20.329 That definition looks impossible to verify, 00:07:20.412 --> 00:07:23.745 because NP contains infinitely many problems. 00:07:24.197 --> 00:07:29.050 Cook and Levin did the impossible part once, in nineteen seventy one, by encoding 00:07:29.050 --> 00:07:34.171 an arbitrary polynomial-time verification directly as a Boolean formula. 00:07:34.967 --> 00:07:37.417 Three satisfiability, the restriction 00:07:37.417 --> 00:07:42.155 where every clause has exactly three literals, is NP-complete too. 00:07:42.351 --> 00:07:45.742 So nobody after them has to go back to Turing machines. 00:07:45.939 --> 00:07:50.467 You reduce three satisfiability into your problem, and transitivity carries all 00:07:50.467 --> 00:07:52.232 of NP along behind. 00:07:53.029 --> 00:07:57.163 Which is exactly what we are going to do now, once, in full. 00:07:58.234 --> 00:08:00.162 Three satisfiability. 00:08:00.475 --> 00:08:03.878 You are handed a Boolean formula in one fixed shape. 00:08:04.074 --> 00:08:07.720 It is a conjunction of clauses, and each clause is a disjunction 00:08:07.720 --> 00:08:13.491 of exactly three literals, where a literal means a variable or the negation of one. 00:08:14.403 --> 00:08:16.215 The question is whether some assignment 00:08:16.215 --> 00:08:20.592 of true and false to the variables makes the whole formula come out true. 00:08:20.789 --> 00:08:24.551 And here is the formula we are going to carry for the rest of the lecture. 00:08:24.930 --> 00:08:27.320 Three variables and two clauses. 00:08:27.403 --> 00:08:31.990 The first clause is x one or x two or not x three. 00:08:32.187 --> 00:08:36.852 The second is not x one or not x two or x three. 00:08:36.935 --> 00:08:41.661 Small enough to settle by inspection, which is exactly why it is safe to use. 00:08:42.365 --> 00:08:45.210 We are not going to be clever about this formula. 00:08:45.314 --> 00:08:49.611 We are going to translate it, mechanically, into a graph and a number. 00:08:49.715 --> 00:08:52.151 The translator is built from two pieces, 00:08:52.234 --> 00:08:55.195 one for each kind of object a formula contains. 00:08:56.592 --> 00:08:59.843 First piece: one gadget for every variable. 00:09:00.040 --> 00:09:05.300 It is a single edge, and its two endpoints are the two literals of that variable. 00:09:05.404 --> 00:09:08.354 x on one side, not x on the other. 00:09:09.406 --> 00:09:13.421 A cover has to touch every edge of the graph, and this is an edge. 00:09:13.504 --> 00:09:17.487 So any cover at all contains at least one of these two vertices. 00:09:17.684 --> 00:09:21.087 That is a cost we are going to charge for in a moment. 00:09:21.790 --> 00:09:24.972 And here is the reading that makes the entire proof work. 00:09:25.076 --> 00:09:28.165 Which endpoint the cover takes is a truth value. 00:09:28.361 --> 00:09:31.172 Take the x side and we call x true. 00:09:31.276 --> 00:09:34.538 Take the not x side and we call x false. 00:09:34.851 --> 00:09:36.605 The gadget is a switch. 00:09:37.518 --> 00:09:38.830 Second piece: 00:09:39.027 --> 00:09:41.257 one gadget for every clause. 00:09:41.453 --> 00:09:45.329 It is a triangle, and its three vertices are the clause's three literals, 00:09:45.412 --> 00:09:46.981 one copy of each. 00:09:47.777 --> 00:09:52.503 A triangle has three edges, and no single vertex touches all three. 00:09:52.699 --> 00:09:54.451 Take just the top one: 00:09:54.534 --> 00:09:58.134 it meets two of the edges and misses the bottom edge entirely. 00:09:58.237 --> 00:10:00.514 So one vertex is never enough. 00:10:01.217 --> 00:10:05.432 Take any two of them and every edge is covered, whichever two you choose. 00:10:05.745 --> 00:10:08.890 So each triangle costs at least two vertices. 00:10:08.973 --> 00:10:11.191 Equivalently, exactly one of the three 00:10:11.191 --> 00:10:15.650 can be left outside the cover, and that fact is what the whole proof will lean on. 00:10:16.446 --> 00:10:20.000 Third piece, and this one is not a gadget but a wire. 00:10:20.196 --> 00:10:22.203 For every literal in every clause, 00:10:22.286 --> 00:10:27.082 join that clause vertex to the variable gadget vertex carrying the same literal. 00:10:27.878 --> 00:10:32.778 Here the triangle's x vertex is wired back to the x endpoint upstairs. 00:10:32.975 --> 00:10:36.700 The other two literals of this clause would run off to their own gadgets, 00:10:36.783 --> 00:10:38.421 which I have not drawn. 00:10:39.473 --> 00:10:41.213 That is the whole construction. 00:10:41.296 --> 00:10:46.252 Two vertices and one edge per variable, three vertices and three edges per clause, 00:10:46.335 --> 00:10:48.309 and one wire per literal. 00:10:48.413 --> 00:10:51.049 Nothing depends on anything being clever. 00:10:51.753 --> 00:10:53.461 And now the number. 00:10:53.657 --> 00:10:58.534 With n variables and m clauses, set k to n plus two m. 00:10:58.638 --> 00:11:02.119 One vertex per variable gadget, two per clause gadget, 00:11:02.202 --> 00:11:04.653 and not a single vertex to spare. 00:11:05.449 --> 00:11:08.095 That tightness is the engine of the whole proof. 00:11:08.178 --> 00:11:14.271 The gadgets force n, the triangles force two m, those vertex sets do not overlap, 00:11:14.354 --> 00:11:16.839 so every cover has at least that many. 00:11:16.943 --> 00:11:20.427 Asking for exactly that many leaves no freedom anywhere. 00:11:21.583 --> 00:11:25.392 Here is our formula again, and here is the graph it becomes. 00:11:25.588 --> 00:11:28.782 Three variables, so three variable gadgets. 00:11:28.886 --> 00:11:33.739 One edge each, six vertices in all, one pair per variable. 00:11:34.443 --> 00:11:36.987 Two clauses, so two triangles. 00:11:37.183 --> 00:11:41.175 The first clause is x one or x two or not x three, 00:11:41.259 --> 00:11:46.147 and its triangle carries exactly those three literals, one vertex each. 00:11:46.572 --> 00:11:50.645 The second clause is not x one or not x two or x three, 00:11:50.729 --> 00:11:53.075 and its triangle carries those. 00:11:53.271 --> 00:11:56.311 Notice that every literal now appears twice over. 00:11:56.395 --> 00:12:00.064 Once up in a gadget, and once down in a triangle. 00:12:00.977 --> 00:12:02.464 Now the wires. 00:12:02.916 --> 00:12:06.945 Every clause vertex joins the gadget vertex with the same label. 00:12:07.049 --> 00:12:11.876 The x one copy runs up to x one, the x two copy runs to x two, 00:12:11.960 --> 00:12:15.711 and the not x three copy runs all the way across the picture. 00:12:16.508 --> 00:12:19.039 The second triangle wires the same way. 00:12:19.143 --> 00:12:24.751 Not x one, not x two, and x three, each to its own endpoint upstairs. 00:12:25.064 --> 00:12:27.457 Six literals, six wires. 00:12:28.253 --> 00:12:31.110 Twelve vertices and fifteen edges. 00:12:31.307 --> 00:12:32.558 Look at how that was built. 00:12:32.642 --> 00:12:34.404 One pass over the formula, 00:12:34.488 --> 00:12:39.620 writing down a fixed number of vertices and edges per variable and per clause. 00:12:39.724 --> 00:12:44.612 That is the polynomial-time half of the reduction, and it is the easy half. 00:12:46.009 --> 00:12:47.086 Now the number. 00:12:47.170 --> 00:12:50.801 Each of the three variable edges demands at least one vertex, 00:12:50.885 --> 00:12:52.953 because a cover has to touch it. 00:12:53.149 --> 00:12:56.018 Three edges, one apiece, so three. 00:12:56.814 --> 00:13:01.041 Each of the two triangles demands at least two, as we showed. 00:13:01.354 --> 00:13:04.118 Two triangles, two apiece, so four. 00:13:04.314 --> 00:13:08.947 And those five demands sit on completely separate vertices, so they simply add. 00:13:09.430 --> 00:13:11.463 Rule a line under them and add. 00:13:11.915 --> 00:13:15.941 Seven. Every vertex cover of this graph has at least seven vertices, 00:13:16.025 --> 00:13:20.321 whatever it looks like, and seven is exactly the budget the construction sets. 00:13:21.233 --> 00:13:26.072 So asking for a cover of size seven is asking for one with no slack at all. 00:13:26.156 --> 00:13:28.754 Exactly one endpoint from each variable edge. 00:13:28.838 --> 00:13:31.389 Exactly two vertices from each triangle. 00:13:31.473 --> 00:13:33.935 Nothing left over to patch anything up with. 00:13:35.076 --> 00:13:40.832 Take the formula's side first. Set x one true, x two false, and x three true. 00:13:40.916 --> 00:13:42.914 Check it against both clauses. 00:13:43.699 --> 00:13:47.786 Clause one is x one or x two or not x three. 00:13:47.878 --> 00:13:51.246 Its first literal is true, so the clause holds. 00:13:51.419 --> 00:13:56.899 Clause two is not x one or not x two or x three, and not x two is true, 00:13:56.899 --> 00:13:58.758 since x two is false. 00:13:58.861 --> 00:14:02.322 Both clauses hold, so the formula is satisfied. 00:14:03.118 --> 00:14:05.581 Now build the cover from that assignment. 00:14:05.777 --> 00:14:10.167 From each variable gadget, take the endpoint whose literal came out true. 00:14:10.363 --> 00:14:13.081 x one true, so take x one. 00:14:13.277 --> 00:14:16.273 x two false, so take not x two. 00:14:16.470 --> 00:14:19.269 x three true, so take x three. 00:14:20.065 --> 00:14:22.063 Three vertices so far. 00:14:22.260 --> 00:14:26.680 Now each triangle. Look at which of its literals the assignment made true, 00:14:26.764 --> 00:14:30.829 pick one of those, and leave that vertex out. Take the other two. 00:14:31.626 --> 00:14:34.332 In the first triangle, x one is true. 00:14:34.435 --> 00:14:40.508 So leave the x one copy outside, and take the x two copy and the not x three copy. 00:14:41.305 --> 00:14:44.324 In the second triangle, not x two is true. 00:14:44.521 --> 00:14:48.759 So leave the not x two copy outside, and take the other two. 00:14:48.955 --> 00:14:52.958 Two from each triangle, four in all, and three plus four is seven. 00:14:53.042 --> 00:14:54.622 Exactly the budget. 00:14:55.674 --> 00:14:58.124 Now the part that could actually fail. 00:14:58.321 --> 00:15:00.493 Is every edge of this graph covered? 00:15:00.805 --> 00:15:03.999 There are three families to check, and I will take them in order. 00:15:04.702 --> 00:15:06.642 The three variable edges. 00:15:07.442 --> 00:15:11.201 We took one endpoint of each of them by construction, so all three are covered, 00:15:11.285 --> 00:15:13.260 and there is nothing to argue. 00:15:13.963 --> 00:15:15.996 The six triangle edges. 00:15:16.100 --> 00:15:19.034 We took two of the three vertices of each triangle, 00:15:19.118 --> 00:15:22.706 and two vertices of a triangle meet all three of its edges. 00:15:22.810 --> 00:15:24.947 So all six are covered as well. 00:15:25.744 --> 00:15:28.508 The six wires are the interesting family. 00:15:28.611 --> 00:15:30.884 If a wire's clause end is in the cover, 00:15:30.968 --> 00:15:33.801 that wire is covered and there is nothing to prove. 00:15:34.114 --> 00:15:35.159 So the only wires 00:15:35.159 --> 00:15:38.945 at risk are the two hanging off the vertices we deliberately left out. 00:15:39.648 --> 00:15:41.902 And look where those two wires go. 00:15:42.214 --> 00:15:46.008 The excluded vertex in the first triangle is the copy of x one, 00:15:46.092 --> 00:15:50.362 and its wire runs up to the gadget vertex x one, which is in the cover, 00:15:50.446 --> 00:15:53.012 because the assignment made x one true. 00:15:53.809 --> 00:15:55.757 Same story in the second triangle. 00:15:55.841 --> 00:16:01.213 The excluded vertex is the copy of not x two, its wire runs up to not x two, 00:16:01.297 --> 00:16:06.116 and we took not x two into the cover precisely because x two is false. 00:16:06.220 --> 00:16:08.276 Both risky wires are covered. 00:16:08.887 --> 00:16:11.252 That is the forward direction complete. 00:16:11.336 --> 00:16:14.611 And notice exactly where satisfaction was used. 00:16:14.715 --> 00:16:18.427 The vertex we leave out of a triangle has to be a true literal, 00:16:18.511 --> 00:16:22.494 and true literals are precisely the ones the gadgets put into the cover. 00:16:22.598 --> 00:16:25.919 An unsatisfied clause would have nothing safe to leave out. 00:16:27.432 --> 00:16:28.706 Now run it backwards, 00:16:28.790 --> 00:16:31.728 which is the direction that actually carries the theorem. 00:16:31.925 --> 00:16:35.138 Somebody hands you a cover of size seven for this graph. 00:16:35.222 --> 00:16:39.507 They will not say where they got it, and it need not be the one we just built. 00:16:40.303 --> 00:16:42.731 The counting does the first job for us. 00:16:42.927 --> 00:16:47.873 Seven vertices, and we proved the minimum is seven, so there is no slack anywhere. 00:16:48.325 --> 00:16:50.970 Exactly one endpoint of each variable edge, 00:16:51.054 --> 00:16:54.062 and exactly two vertices of each triangle. 00:16:54.765 --> 00:16:57.692 So read the assignment straight off the top row. 00:16:57.888 --> 00:17:04.062 This cover took not x one, so x one is false. It took x two, so x two is true. 00:17:04.146 --> 00:17:07.870 It took not x three, so x three is false. 00:17:07.954 --> 00:17:12.599 Well defined, precisely because exactly one of each pair was taken. 00:17:13.395 --> 00:17:16.008 Does that assignment satisfy the formula? 00:17:16.460 --> 00:17:19.163 Here is the argument, and it takes three steps. 00:17:19.247 --> 00:17:22.730 In each triangle exactly one vertex is left out. 00:17:22.927 --> 00:17:26.887 In the first triangle, the excluded vertex is the copy of x two. 00:17:27.683 --> 00:17:31.759 That vertex has a wire running up to the gadget vertex x two. 00:17:31.956 --> 00:17:35.347 The wire is an edge, and every edge is covered. 00:17:35.543 --> 00:17:39.236 Its clause end is not in the cover, so its other end must be. 00:17:39.432 --> 00:17:42.475 The gadget vertex x two is in the cover. 00:17:42.854 --> 00:17:46.964 And a gadget vertex in the cover is a literal we are calling true. 00:17:47.068 --> 00:17:48.714 So x two is true, 00:17:48.798 --> 00:17:53.989 and x two is one of the three literals of this first triangle, which is clause one. 00:17:54.302 --> 00:17:58.842 Clause one is satisfied, and we never had to look at its other two literals. 00:17:59.638 --> 00:18:02.240 The second triangle goes the same way. 00:18:02.436 --> 00:18:07.428 The excluded vertex is the copy of not x one, its wire forces not x one 00:18:07.428 --> 00:18:11.826 into the cover, and not x one in the cover means x one is false. 00:18:11.910 --> 00:18:15.986 That literal belongs to clause two, so clause two is satisfied too. 00:18:16.782 --> 00:18:20.251 Both clauses satisfied, so the formula is satisfiable, 00:18:20.335 --> 00:18:23.412 and the assignment we read off the cover is the witness. 00:18:23.864 --> 00:18:25.978 Note what carried that argument. 00:18:26.175 --> 00:18:27.428 Not the cover's cleverness, 00:18:27.428 --> 00:18:31.063 but the fact that seven left it no room to be anything else. 00:18:32.158 --> 00:18:34.862 So let us say precisely what we now have. 00:18:34.945 --> 00:18:38.602 A function that takes a three satisfiability formula and returns 00:18:38.602 --> 00:18:44.257 a graph together with a number, computable in time linear in the size of the formula. 00:18:45.053 --> 00:18:49.488 And a proof, in both directions, that the formula is satisfiable exactly 00:18:49.488 --> 00:18:53.367 when that graph has a vertex cover of size at most k. 00:18:53.680 --> 00:18:58.359 That is the definition of a polynomial-time reduction, met in full. 00:18:59.156 --> 00:19:02.454 Three satisfiability reduces to vertex cover. 00:19:02.558 --> 00:19:06.656 Now read that as a statement about vertex cover, which is what it is. 00:19:06.853 --> 00:19:09.684 Cook and Levin put satisfiability at the top, 00:19:09.767 --> 00:19:12.926 with every problem in NP reducing into it. 00:19:13.722 --> 00:19:16.995 Satisfiability reduces to three satisfiability, 00:19:17.078 --> 00:19:20.758 and our arrow carries the hardness one step further along. 00:19:20.955 --> 00:19:23.391 So vertex cover is NP-hard: 00:19:23.474 --> 00:19:27.736 every problem in NP reduces to it, by composing the arrows. 00:19:28.649 --> 00:19:33.363 And vertex cover is in NP, which we settled in the first few minutes. 00:19:33.560 --> 00:19:38.109 Hand me a set of vertices and I will check it against every edge in linear time. 00:19:38.192 --> 00:19:43.185 NP-hard and in NP: vertex cover is NP-complete. 00:19:43.889 --> 00:19:48.984 Now read the arrows once more, because the direction is the whole examinable content. 00:19:49.067 --> 00:19:52.769 The arrow runs from the problem already known to be hard into the new one, 00:19:52.852 --> 00:19:54.315 never the other way. 00:19:55.019 --> 00:19:57.075 What it says is a conditional. 00:19:57.178 --> 00:19:59.698 If you could solve vertex cover quickly, you 00:19:59.698 --> 00:20:04.781 could solve three satisfiability quickly, and therefore everything in NP quickly. 00:20:04.864 --> 00:20:08.894 It does not say the reverse, and it hands you no algorithm at all. 00:20:10.290 --> 00:20:14.923 Which brings us to the last point, and it is the one worth carrying out of the room. 00:20:15.120 --> 00:20:19.472 NP-hardness is not a proof that no fast algorithm exists. 00:20:19.555 --> 00:20:24.188 Nobody has proved that about any problem in NP, and nobody is close. 00:20:24.892 --> 00:20:27.110 What it is, is a ranking. 00:20:27.214 --> 00:20:31.102 Vertex cover sits at least as high as every problem in the class. 00:20:31.185 --> 00:20:34.294 So if you ever find a polynomial-time algorithm for it, 00:20:34.377 --> 00:20:36.198 you have not found an exception. 00:20:36.281 --> 00:20:41.426 You have proved P equals NP, and thousands of problems fall in the same instant. 00:20:41.967 --> 00:20:45.393 And that is exactly why the phrase describes the problem. 00:20:45.589 --> 00:20:49.677 The reduction is a construction on a page, checkable by anyone. 00:20:49.873 --> 00:20:53.611 It was true before you attempted the problem, it is true while you are stuck 00:20:53.611 --> 00:20:57.792 on it, and it will still be true long after P versus NP is settled. 00:20:58.588 --> 00:21:01.036 It says nothing whatsoever about you. 00:21:01.119 --> 00:21:03.535 It says where the problem stands.