# NP-Completeness and Reduction: From Definitions to the 3-SAT to Vertex Cover Proof > A verifier-first introduction to P and NP, followed by the 3-SAT to Vertex Cover reduction carried out completely. Vertex Cover is posed as a decision problem and checked against a certificate; P and NP are defined by what a polynomial-time verifier can confirm; polynomial-time reductions are defined and their direction fixed. The centrepiece is one full construction: variable gadgets, clause gadgets and the wires between them, drawn on a three-variable, two-clause formula, with the budget argument and both directions of the correspondence argued on that concrete graph, using two different covers. The closing section states exactly what the reduction proves, in which direction it runs, and why NP-hardness is a theorem about a problem rather than a verdict on whoever failed to solve it. - Canonical watch page: [NP-Completeness and Reduction: From Definitions to the 3-SAT to Vertex Cover Proof](https://academa.ai/lectures/three-sat-vertex-cover-reduction) - Publisher: [Academa, Inc.](https://academa.ai) - Subject: Computer Science - Published: 2026-08-28T18:50:14.620Z - Updated: 2026-08-28T18:50:14.620Z - Duration: PT1262S (21 minutes 2 seconds) - Chapters: 5 - Views: 0 - Language: en-US - Access: Free - Video stream: [HLS content](https://academa.ai/media/l/01M14TXPGH643NHQ5B5ZQFEB15/0/dark/master.m3u8) - Audiovisual record: [Semantic JSON](https://academa.ai/media/l/01M14TXPGH643NHQ5B5ZQFEB15/0/semantic.json) - Thumbnail: [Image](https://academa.ai/media/l/01M14TXPGH643NHQ5B5ZQFEB15/0/dark/poster.jpg) ## Description P and NP defined by verifiers, then the 3-SAT to Vertex Cover reduction built and argued in both directions on one formula. ## Chapters - [00:00–04:19.364 · Checking Is Not Finding](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=0) - [04:19.364–07:57.169 · What a Reduction Proves](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=259.36350000000004) - [07:57.169–11:21.002 · Two Gadgets](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=477.16945833333335) - [11:21.002–18:27.959 · One Formula, One Graph](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=681.0023541666667) - [18:27.959–21:02 · What Was Proved](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1107.9585208333333) ## Transcript ### [00:00 · Checking Is Not Finding](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=0) 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? ### [04:19.364 · What a Reduction Proves](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=259.36350000000004) 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. ### [07:57.169 · Two Gadgets](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=477.16945833333335) 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. ### [11:21.002 · One Formula, One Graph](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=681.0023541666667) 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. ### [18:27.959 · What Was Proved](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1107.9585208333333) 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. ## About Academa, Inc. Academa makes technical knowledge easier to understand through visual lectures and lets learners request new lecture videos on the topics they need. ## Complete audiovisual record Immutable source: [semantic.json](https://academa.ai/media/l/01M14TXPGH643NHQ5B5ZQFEB15/0/semantic.json) Record version: 1. Render attempt: 0. ### How to read this timeline Each scene owns its object identifiers. A beat's board is the complete board when listed, empty when marked empty, and unchanged from the nearest earlier listed board in the same scene when marked unchanged. Action times are absolute positions in the published video. ### Scene 1: [Checking Is Not Finding](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=0) Span: 00:00–04:19.364 (0s–259.36350000000004s). #### Objects - card: a Title that says "Computational Complexity — NP-Completeness and Reduction: From Definitions to the 3-SAT to Vertex Cover Proof" - cond1: a Math \[text\] that says "$upright("time") \<= p(\|w\|)$" - cond2: a Math \[text\] that says "$w in L arrow.r.double exists c: V(w, c) = 1$" - cond3: a Math \[text\] that says "$w in.not L arrow.r.double forall c: V(w, c) = 0$" - cover\_note: a Panel that says "A vertex cover of $G$ is a set $S$ of vertices such that every edge of $G$ has at least one endpoint in $S$." - decision: a Text \[text\] that says "Decision problem $upright("VC")$: given a graph $G$ and a number $k$, does $G$ have a vertex cover with at most $k$ vertices?" - e\_ab: a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)) - e\_bc: a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)) - e\_be: a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)) - e\_cd: a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)) - e\_de: a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)) - e\_ef: a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)) - e\_fa: a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)) - edge\_check: a Tex \[text\] that says "Every edge has an endpoint in $S$." - g: a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)) - head\_check: a Heading that says "Checking a Proposed Answer" - head\_classes: a Heading that says "The Two Classes" - head\_cover: a Heading that says "A Set That Touches Every Edge" - head\_np: a Heading that says "The Verifier" - inclusion: a Math \[text\] that says "$upright("P") subset.eq upright("NP")$" - instance: a Math \[text\] that says "$chevron.l G, 3 chevron.r$" - np\_panel: a Panel that says "$L in upright("NP")$ when some polynomial-time verifier satisfies all three conditions above." - p\_panel: a Panel that says "$L in upright("P")$ when some algorithm decides $L$ in polynomial time, with no certificate offered." - point: a Point \[yellow\] drawn in g (location=(3.3, 4.5)) - point\_2: a Point \[yellow\] drawn in g (location=(5.5, 1.0)) - point\_3: a Point \[yellow\] drawn in g (location=(1.1, 1.0)) - point\_4: a Point \[yellow\] drawn in g (location=(3.3, 4.5)) - size\_check: a Math \[text\] that says "$\|S\| = 3 \<= k$" - va: a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12) - vb: a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12) - vc: a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12) - vd: a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12) - ve: a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12) - verdict: a Math \[text\] that says "$V(chevron.l G, 3 chevron.r, S) = upright("accept")$" - verifier\_intro: a Text \[text\] that says "A verifier $V(w, c)$ reads the instance $w$ and a second string $c$, the certificate." - vf: a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12) #### Beats ##### [00:00](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=0) Narration: 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. Board: Empty. Actions: - [00:00](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=0): card is shown on the screen, written out. - [00:1.5](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1.5): card: enter:write-left-to-right. ##### [00:12.697](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=12.6975) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [00:24.505](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=24.505499999999998): card is hidden from the screen — left the board. ##### [00:25.706](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=25.7055) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [00:25.706](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=25.7055): head\_cover is shown on the screen, written out. - [00:25.706](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=25.7055): g is shown on the screen, written out. - [00:28.039](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=28.039): va is shown on the screen, written out. - [00:28.129](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=28.129): vb is shown on the screen, written out. - [00:28.219](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=28.219): vc is shown on the screen, written out. - [00:28.309](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=28.309): vd is shown on the screen, written out. - [00:28.399](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=28.399): ve is shown on the screen, written out. - [00:28.489](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=28.489): vf is shown on the screen, written out. - [00:29.362](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=29.362000000000002): e\_ab is shown on the screen, drawn. - [00:29.452](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=29.452): e\_bc is shown on the screen, drawn. - [00:29.542](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=29.542): e\_cd is shown on the screen, drawn. - [00:29.632](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=29.632): e\_de is shown on the screen, drawn. - [00:29.722](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=29.722): e\_ef is shown on the screen, drawn. - [00:29.812](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=29.812): e\_fa is shown on the screen, drawn. - [00:29.902](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=29.902): e\_be is shown on the screen, drawn. ##### [00:36.847](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=36.8475) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); head\_cover — a Heading that says "A Set That Touches Every Edge"; va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)) Actions: - [00:40.772](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=40.772): g moves to a new place on the board. - [00:40.772](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=40.772): cover\_note is shown on the screen, written out. ##### [00:49.603](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=49.602999999999994) Narration: 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. Board: cover\_note — a Panel that says "A vertex cover of $G$ is a set $S$ of vertices such that every edge of $G$ has at least one endpoint in $S$."; g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); head\_cover — a Heading that says "A Set That Touches Every Edge"; va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)) Actions: - [00:53.806](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=53.806): decision is shown on the screen, written out. - [01:1.816](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=61.815999999999995): instance is shown on the screen, written out. ##### [01:3.264](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=63.263999999999996) Narration: 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. Board: cover\_note — a Panel that says "A vertex cover of $G$ is a set $S$ of vertices such that every edge of $G$ has at least one endpoint in $S$."; decision — a Text \[text\] that says "Decision problem $upright("VC")$: given a graph $G$ and a number $k$, does $G$ have a vertex cover with at most $k$ vertices?"; instance — a Math \[text\] that says "$chevron.l G, 3 chevron.r$"; g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); head\_cover — a Heading that says "A Set That Touches Every Edge"; va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)) Actions: - [01:6.015](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=66.01499999999999): vb is emphasized. - [01:6.365](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=66.36499999999998): vd is emphasized. - [01:6.715](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=66.71499999999997): vf is emphasized. - [01:17.614](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=77.61399999999999): cover\_note is hidden from the screen — left the board. - [01:17.614](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=77.61399999999999): decision is hidden from the screen — left the board. - [01:17.614](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=77.61399999999999): head\_cover is hidden from the screen — left the board. - [01:17.614](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=77.61399999999999): instance is hidden from the screen — left the board. ##### [01:18.214](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=78.214) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)) Actions: - [01:18.214](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=78.214): head\_check is shown on the screen, written out. - [01:23.566](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=83.56600000000002): size\_check is shown on the screen, written out. - [01:27.444](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=87.444): e\_ab is indicated — a transient flash. - [01:27.944](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=87.944): e\_bc is indicated — a transient flash. - [01:28.444](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=88.444): e\_cd is indicated — a transient flash. - [01:28.944](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=88.944): e\_de is indicated — a transient flash. - [01:29.444](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=89.444): e\_ef is indicated — a transient flash. - [01:29.944](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=89.944): e\_fa is indicated — a transient flash. - [01:30.444](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=90.444): e\_be is indicated — a transient flash. ##### [01:30.609](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=90.6095) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)); size\_check — a Math \[text\] that says "$\|S\| = 3 \<= k$"; head\_check — a Heading that says "Checking a Proposed Answer" Actions: - [01:32.548](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=92.548): edge\_check is shown on the screen, written out. - [01:35.3](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=95.30000000000001): verdict is shown on the screen, written out. ##### [01:45.513](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=105.51299999999999) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)); size\_check — a Math \[text\] that says "$\|S\| = 3 \<= k$"; edge\_check — a Tex \[text\] that says "Every edge has an endpoint in $S$."; verdict — a Math \[text\] that says "$V(chevron.l G, 3 chevron.r, S) = upright("accept")$"; head\_check — a Heading that says "Checking a Proposed Answer" Actions: - [01:49.17](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=109.17): point is shown on the screen, grown. - [01:51.17](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=111.17): point is hidden from the screen. - [01:51.57](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=111.57000000000001): point\_2 is shown on the screen, grown. - [01:53.57](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=113.57000000000001): point\_2 is hidden from the screen. - [01:53.97](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=113.97000000000001): point\_3 is shown on the screen, grown. - [01:55.97](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=115.97000000000001): point\_3 is hidden from the screen. ##### [01:59.882](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=119.8825) Narration: That gap, between checking an answer and finding one, is the whole of what NP is about. So let us make it precise. Board: Unchanged from the preceding beat in this scene. Actions: - [02:7.231](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=127.2315): edge\_check is hidden from the screen — left the board. - [02:7.231](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=127.2315): head\_check is hidden from the screen — left the board. - [02:7.231](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=127.2315): size\_check is hidden from the screen — left the board. - [02:7.231](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=127.2315): verdict is hidden from the screen — left the board. ##### [02:8.431](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=128.4315) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)) Actions: - [02:8.431](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=128.4315): head\_np is shown on the screen, written out. - [02:10.405](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=130.405): verifier\_intro is shown on the screen, written out. ##### [02:21.895](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=141.895) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)); verifier\_intro — a Text \[text\] that says "A verifier $V(w, c)$ reads the instance $w$ and a second string $c$, the certificate."; head\_np — a Heading that says "The Verifier" Actions: - [02:25.703](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=145.703): cond1 is shown on the screen, written out. ##### [02:35.603](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=155.603) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)); verifier\_intro — a Text \[text\] that says "A verifier $V(w, c)$ reads the instance $w$ and a second string $c$, the certificate."; cond1 — a Math \[text\] that says "$upright("time") \<= p(\|w\|)$"; head\_np — a Heading that says "The Verifier" Actions: - [02:36.079](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=156.079): cond2 is shown on the screen, written out. - [02:41.756](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=161.756): cond3 is shown on the screen, written out. ##### [02:52.358](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=172.358) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)); verifier\_intro — a Text \[text\] that says "A verifier $V(w, c)$ reads the instance $w$ and a second string $c$, the certificate."; cond1 — a Math \[text\] that says "$upright("time") \<= p(\|w\|)$"; cond2 — a Math \[text\] that says "$w in L arrow.r.double exists c: V(w, c) = 1$"; cond3 — a Math \[text\] that says "$w in.not L arrow.r.double forall c: V(w, c) = 0$"; head\_np — a Heading that says "The Verifier" Actions: - [03:1.663](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=181.66299999999998): cond2 (the "exists c" part) is indicated — a transient flash. - [03:5.983](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=185.98250000000002): cond1 is hidden from the screen — left the board. - [03:5.983](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=185.98250000000002): cond2 is hidden from the screen — left the board. - [03:5.983](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=185.98250000000002): cond3 is hidden from the screen — left the board. - [03:5.983](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=185.98250000000002): head\_np is hidden from the screen — left the board. - [03:5.983](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=185.98250000000002): verifier\_intro is hidden from the screen — left the board. ##### [03:7.183](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=187.1825) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)) Actions: - [03:7.183](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=187.1825): head\_classes is shown on the screen, written out. - [03:9.807](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=189.80700000000002): p\_panel is shown on the screen, written out. ##### [03:18.534](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=198.5335) Narration: NP is the class we have just built. A polynomial-time verifier, and a short certificate for every yes instance. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)); p\_panel — a Panel that says "$L in upright("P")$ when some algorithm decides $L$ in polynomial time, with no certificate offered."; head\_classes — a Heading that says "The Two Classes" Actions: - [03:20.925](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=200.925): np\_panel is shown on the screen, written out. ##### [03:27.644](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=207.644) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)); p\_panel — a Panel that says "$L in upright("P")$ when some algorithm decides $L$ in polynomial time, with no certificate offered."; np\_panel — a Panel that says "$L in upright("NP")$ when some polynomial-time verifier satisfies all three conditions above."; head\_classes — a Heading that says "The Two Classes" Actions: - [03:29.502](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=209.502): inclusion is shown on the screen, written out. ##### [03:42.118](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=222.118) Narration: 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. Board: g — a Figure (x\_range=(0.0, 6.6), y\_range=(-0.7, 5.1), aspect=(6.6, 5.8)); va — a Point \[blue\] labelled "a" drawn in g (location=(1.1, 3.2), marker\_radius=0.12); vb — a Point \[blue\] labelled "b" drawn in g (location=(3.3, 4.5), marker\_radius=0.12); vc — a Point \[blue\] labelled "c" drawn in g (location=(5.5, 3.2), marker\_radius=0.12); vd — a Point \[blue\] labelled "d" drawn in g (location=(5.5, 1.0), marker\_radius=0.12); ve — a Point \[blue\] labelled "e" drawn in g (location=(3.3, -0.3), marker\_radius=0.12); vf — a Point \[blue\] labelled "f" drawn in g (location=(1.1, 1.0), marker\_radius=0.12); e\_ab — a Line \[gray\] drawn in g (start=(1.1, 3.2), end=(3.3, 4.5)); e\_bc — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(5.5, 3.2)); e\_cd — a Line \[gray\] drawn in g (start=(5.5, 3.2), end=(5.5, 1.0)); e\_de — a Line \[gray\] drawn in g (start=(5.5, 1.0), end=(3.3, -0.3)); e\_ef — a Line \[gray\] drawn in g (start=(3.3, -0.3), end=(1.1, 1.0)); e\_fa — a Line \[gray\] drawn in g (start=(1.1, 1.0), end=(1.1, 3.2)); e\_be — a Line \[gray\] drawn in g (start=(3.3, 4.5), end=(3.3, -0.3)); p\_panel — a Panel that says "$L in upright("P")$ when some algorithm decides $L$ in polynomial time, with no certificate offered."; np\_panel — a Panel that says "$L in upright("NP")$ when some polynomial-time verifier satisfies all three conditions above."; inclusion — a Math \[text\] that says "$upright("P") subset.eq upright("NP")$"; head\_classes — a Heading that says "The Two Classes" Actions: - [03:49.688](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=229.688): point\_4 is shown on the screen, grown. - [03:51.688](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=231.688): point\_4 is hidden from the screen. ##### [03:54.978](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=234.9785) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [04:0.551](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=240.551): vb is indicated — a transient flash. - [04:0.851](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=240.851): vd is indicated — a transient flash. - [04:1.151](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=241.151): vf is indicated — a transient flash. ##### [04:9.29](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=249.2895) Narration: 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? Board: Unchanged from the preceding beat in this scene. Actions: - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): g is hidden from the screen — left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): va is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): vb is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): vc is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): vd is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): ve is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): vf is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): e\_ab is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): e\_bc is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): e\_cd is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): e\_de is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): e\_ef is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): e\_fa is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): e\_be is hidden from the screen — g left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): head\_classes is hidden from the screen — left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): inclusion is hidden from the screen — left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): np\_panel is hidden from the screen — left the board. - [04:18.322](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=258.32183333333336): p\_panel is hidden from the screen — left the board. ### Scene 2: [What a Reduction Proves](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=259.36350000000004) Span: 04:19.364–07:57.169 (259.36350000000004s–477.16945833333335s). #### Objects - arrow\_f: an Arrow \[yellow\] labelled "f" drawn in pipe (start=(2.7, 2.2), end=(4.1, 2.2)) - arrow\_in: an Arrow \[gray\] drawn in pipe (start=(6.9, 2.2), end=(7.9, 2.2)) - arrow\_out: an Arrow \[gray\] drawn in pipe (start=(11.1, 2.2), end=(11.9, 2.2)) - box\_fw: a Polygon \[green\] drawn in pipe (vertices=((4.3, 1.4), (6.7, 1.4), (6.7, 3.0), (4.3, 3.0)), fill\_opacity=0.18) - box\_s: a Polygon \[yellow\] drawn in pipe (vertices=((8.1, 1.4), (10.9, 1.4), (10.9, 3.0), (8.1, 3.0)), fill\_opacity=0.18) - box\_w: a Polygon \[blue\] drawn in pipe (vertices=((0.3, 1.4), (2.5, 1.4), (2.5, 3.0), (0.3, 3.0)), fill\_opacity=0.18) - chain: a Math \[text\] that says "$L \<=\_p upright("3SAT") \<=\_p B$" - complete\_panel: a Panel that says "$B$ is NP-complete when $B$ is NP-hard and $B in upright("NP")$." - cook: a Panel that says "$upright("SAT")$ is NP-complete, and so is $upright("3SAT")$." - dir\_no: a Math \[text\] that says "$A in.not upright("P") quad arrow.r.double quad B in.not upright("P")$" - dir\_yes: a Math \[text\] that says "$B in upright("P") quad arrow.r.double quad A in upright("P")$" - hard\_math: a Math \[text\] that says "$forall L in upright("NP"): thin L \<=\_p B$" - hard\_panel: a Panel that says "$B$ is NP-hard when every problem in NP reduces to $B$ in polynomial time." - head\_complete: a Heading that says "NP-Hard and NP-Complete" - head\_direction: a Heading that says "Which Way Hardness Travels" - head\_reduce: a Heading that says "Borrowing One Solver for Another Problem" - head\_wrong: a Heading that says "The Direction Is the Proof" - lbl\_ans: a Math \[text\] that says "$upright("yes / no")$" drawn in pipe - lbl\_fw: a Math \[green\] that says "$f(w)$" drawn in pipe - lbl\_s: a Math \[yellow\] that says "$upright("solver for ") B$" drawn in pipe - lbl\_w: a Math \[blue\] that says "$w$" drawn in pipe - notation: a Math \[text\] that says "$A \<=\_p B$" - pipe: a Figure (x\_range=(0.0, 13.5), y\_range=(0.0, 4.2), aspect=(13.5, 4.2)) - poly\_line: a Tex \[text\] that says "$f$ is computable in polynomial time." - red\_def: a Math \[text\] that says "$w in A quad arrow.l.r.double quad f(w) in B$" - right\_text: a Text \[text\] that says "Every 3SAT instance becomes a $B$ instance. A fast algorithm for $B$ would settle 3SAT, and with it all of NP. That is a lower bound on $B$." - right\_way: a Math \[text\] that says "$upright("3SAT") \<=\_p B$" - tag\_a: a Math \[blue\] that says "$upright("instance of ") A$" drawn in pipe - tag\_b: a Math \[green\] that says "$upright("instance of ") B$" drawn in pipe - tex: a Tex \[text\] that says "Proves $B$ is hard" - tex\_2: a Tex \[text\] that says "Proves nothing about $B$" - travel: a Tex \[text\] that says "Hardness travels forwards along the arrow." - wrong\_text: a Text \[text\] that says "Every $B$ instance becomes a 3SAT instance. That bounds $B$ from above by a problem nobody can solve quickly, which says nothing about $B$ at all." - wrong\_way: a Math \[text\] that says "$B \<=\_p upright("3SAT")$" #### Beats ##### [04:19.364](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=259.36350000000004) Narration: 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. Board: Empty. Actions: - [04:19.364](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=259.36350000000004): head\_reduce is shown on the screen, written out. - [04:19.364](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=259.36350000000004): pipe is shown on the screen, written out. - [04:20.119](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=260.11850000000004): box\_w is shown on the screen, written out. - [04:20.319](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=260.31850000000003): lbl\_w is shown on the screen, written out. - [04:20.519](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=260.5185): tag\_a is shown on the screen, written out. ##### [04:31.783](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=271.7825) Narration: 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. Board: pipe — a Figure (x\_range=(0.0, 13.5), y\_range=(0.0, 4.2), aspect=(13.5, 4.2)); head\_reduce — a Heading that says "Borrowing One Solver for Another Problem"; box\_w — a Polygon \[blue\] drawn in pipe (vertices=((0.3, 1.4), (2.5, 1.4), (2.5, 3.0), (0.3, 3.0)), fill\_opacity=0.18); lbl\_w — a Math \[blue\] that says "$w$" drawn in pipe; tag\_a — a Math \[blue\] that says "$upright("instance of ") A$" drawn in pipe Actions: - [04:34.779](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=274.77850000000007): arrow\_f is shown on the screen, drawn. - [04:37.124](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=277.12350000000004): box\_fw is shown on the screen, written out. - [04:37.324](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=277.3235): lbl\_fw is shown on the screen, written out. - [04:37.524](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=277.5235): tag\_b is shown on the screen, written out. - [04:38.691](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=278.69050000000004): arrow\_in is shown on the screen, drawn. - [04:38.891](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=278.89050000000003): box\_s is shown on the screen, written out. - [04:39.191](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=279.19050000000004): lbl\_s is shown on the screen, written out. - [04:43.138](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=283.13750000000005): arrow\_out is shown on the screen, drawn. - [04:43.338](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=283.33750000000003): lbl\_ans is shown on the screen, written out. ##### [04:45.201](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=285.20050000000003) Narration: 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. Board: pipe — a Figure (x\_range=(0.0, 13.5), y\_range=(0.0, 4.2), aspect=(13.5, 4.2)); head\_reduce — a Heading that says "Borrowing One Solver for Another Problem"; box\_w — a Polygon \[blue\] drawn in pipe (vertices=((0.3, 1.4), (2.5, 1.4), (2.5, 3.0), (0.3, 3.0)), fill\_opacity=0.18); lbl\_w — a Math \[blue\] that says "$w$" drawn in pipe; tag\_a — a Math \[blue\] that says "$upright("instance of ") A$" drawn in pipe; arrow\_f — an Arrow \[yellow\] labelled "f" drawn in pipe (start=(2.7, 2.2), end=(4.1, 2.2)); box\_fw — a Polygon \[green\] drawn in pipe (vertices=((4.3, 1.4), (6.7, 1.4), (6.7, 3.0), (4.3, 3.0)), fill\_opacity=0.18); lbl\_fw — a Math \[green\] that says "$f(w)$" drawn in pipe; tag\_b — a Math \[green\] that says "$upright("instance of ") B$" drawn in pipe; arrow\_in — an Arrow \[gray\] drawn in pipe (start=(6.9, 2.2), end=(7.9, 2.2)); box\_s — a Polygon \[yellow\] drawn in pipe (vertices=((8.1, 1.4), (10.9, 1.4), (10.9, 3.0), (8.1, 3.0)), fill\_opacity=0.18); lbl\_s — a Math \[yellow\] that says "$upright("solver for ") B$" drawn in pipe; arrow\_out — an Arrow \[gray\] drawn in pipe (start=(11.1, 2.2), end=(11.9, 2.2)); lbl\_ans — a Math \[text\] that says "$upright("yes / no")$" drawn in pipe Actions: - [04:47.755](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=287.75450000000006): red\_def is shown on the screen, written out. - [04:58.482](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=298.48150000000004): red\_def (the "arrow.l.r.double" part) is indicated — a transient flash. ##### [05:0.383](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=300.38250000000005) Narration: And f itself has to be cheap: computable in polynomial time. If translating cost more than solving, the whole arrangement would be pointless. Board: pipe — a Figure (x\_range=(0.0, 13.5), y\_range=(0.0, 4.2), aspect=(13.5, 4.2)); red\_def — a Math \[text\] that says "$w in A quad arrow.l.r.double quad f(w) in B$"; head\_reduce — a Heading that says "Borrowing One Solver for Another Problem"; box\_w — a Polygon \[blue\] drawn in pipe (vertices=((0.3, 1.4), (2.5, 1.4), (2.5, 3.0), (0.3, 3.0)), fill\_opacity=0.18); lbl\_w — a Math \[blue\] that says "$w$" drawn in pipe; tag\_a — a Math \[blue\] that says "$upright("instance of ") A$" drawn in pipe; arrow\_f — an Arrow \[yellow\] labelled "f" drawn in pipe (start=(2.7, 2.2), end=(4.1, 2.2)); box\_fw — a Polygon \[green\] drawn in pipe (vertices=((4.3, 1.4), (6.7, 1.4), (6.7, 3.0), (4.3, 3.0)), fill\_opacity=0.18); lbl\_fw — a Math \[green\] that says "$f(w)$" drawn in pipe; tag\_b — a Math \[green\] that says "$upright("instance of ") B$" drawn in pipe; arrow\_in — an Arrow \[gray\] drawn in pipe (start=(6.9, 2.2), end=(7.9, 2.2)); box\_s — a Polygon \[yellow\] drawn in pipe (vertices=((8.1, 1.4), (10.9, 1.4), (10.9, 3.0), (8.1, 3.0)), fill\_opacity=0.18); lbl\_s — a Math \[yellow\] that says "$upright("solver for ") B$" drawn in pipe; arrow\_out — an Arrow \[gray\] drawn in pipe (start=(11.1, 2.2), end=(11.9, 2.2)); lbl\_ans — a Math \[text\] that says "$upright("yes / no")$" drawn in pipe Actions: - [05:2.171](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=302.17050000000006): poly\_line is shown on the screen, written out. ##### [05:10.456](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=310.45550000000003) Narration: 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. Board: pipe — a Figure (x\_range=(0.0, 13.5), y\_range=(0.0, 4.2), aspect=(13.5, 4.2)); red\_def — a Math \[text\] that says "$w in A quad arrow.l.r.double quad f(w) in B$"; poly\_line — a Tex \[text\] that says "$f$ is computable in polynomial time."; head\_reduce — a Heading that says "Borrowing One Solver for Another Problem"; box\_w — a Polygon \[blue\] drawn in pipe (vertices=((0.3, 1.4), (2.5, 1.4), (2.5, 3.0), (0.3, 3.0)), fill\_opacity=0.18); lbl\_w — a Math \[blue\] that says "$w$" drawn in pipe; tag\_a — a Math \[blue\] that says "$upright("instance of ") A$" drawn in pipe; arrow\_f — an Arrow \[yellow\] labelled "f" drawn in pipe (start=(2.7, 2.2), end=(4.1, 2.2)); box\_fw — a Polygon \[green\] drawn in pipe (vertices=((4.3, 1.4), (6.7, 1.4), (6.7, 3.0), (4.3, 3.0)), fill\_opacity=0.18); lbl\_fw — a Math \[green\] that says "$f(w)$" drawn in pipe; tag\_b — a Math \[green\] that says "$upright("instance of ") B$" drawn in pipe; arrow\_in — an Arrow \[gray\] drawn in pipe (start=(6.9, 2.2), end=(7.9, 2.2)); box\_s — a Polygon \[yellow\] drawn in pipe (vertices=((8.1, 1.4), (10.9, 1.4), (10.9, 3.0), (8.1, 3.0)), fill\_opacity=0.18); lbl\_s — a Math \[yellow\] that says "$upright("solver for ") B$" drawn in pipe; arrow\_out — an Arrow \[gray\] drawn in pipe (start=(11.1, 2.2), end=(11.9, 2.2)); lbl\_ans — a Math \[text\] that says "$upright("yes / no")$" drawn in pipe Actions: - [05:15.878](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=315.87750000000005): notation is shown on the screen, written out. - [05:22.855](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=322.855): pipe moves to a new place on the board. - [05:22.855](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=322.855): head\_reduce is hidden from the screen — left the board. - [05:22.855](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=322.855): notation is hidden from the screen — left the board. - [05:22.855](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=322.855): poly\_line is hidden from the screen — left the board. - [05:22.855](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=322.855): red\_def is hidden from the screen — left the board. ##### [05:24.055](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=324.05500000000006) Narration: 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. Board: pipe — a Figure (x\_range=(0.0, 13.5), y\_range=(0.0, 4.2), aspect=(13.5, 4.2)); box\_w — a Polygon \[blue\] drawn in pipe (vertices=((0.3, 1.4), (2.5, 1.4), (2.5, 3.0), (0.3, 3.0)), fill\_opacity=0.18); lbl\_w — a Math \[blue\] that says "$w$" drawn in pipe; tag\_a — a Math \[blue\] that says "$upright("instance of ") A$" drawn in pipe; arrow\_f — an Arrow \[yellow\] labelled "f" drawn in pipe (start=(2.7, 2.2), end=(4.1, 2.2)); box\_fw — a Polygon \[green\] drawn in pipe (vertices=((4.3, 1.4), (6.7, 1.4), (6.7, 3.0), (4.3, 3.0)), fill\_opacity=0.18); lbl\_fw — a Math \[green\] that says "$f(w)$" drawn in pipe; tag\_b — a Math \[green\] that says "$upright("instance of ") B$" drawn in pipe; arrow\_in — an Arrow \[gray\] drawn in pipe (start=(6.9, 2.2), end=(7.9, 2.2)); box\_s — a Polygon \[yellow\] drawn in pipe (vertices=((8.1, 1.4), (10.9, 1.4), (10.9, 3.0), (8.1, 3.0)), fill\_opacity=0.18); lbl\_s — a Math \[yellow\] that says "$upright("solver for ") B$" drawn in pipe; arrow\_out — an Arrow \[gray\] drawn in pipe (start=(11.1, 2.2), end=(11.9, 2.2)); lbl\_ans — a Math \[text\] that says "$upright("yes / no")$" drawn in pipe Actions: - [05:24.055](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=324.05500000000006): head\_direction is shown on the screen, written out. - [05:30.034](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=330.0335): dir\_yes is shown on the screen, written out. - [05:35.619](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=335.61850000000004): arrow\_f is indicated — a transient flash. - [05:36.594](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=336.59350000000006): box\_s is indicated — a transient flash. ##### [05:40.236](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=340.2355) Narration: 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. Board: pipe — a Figure (x\_range=(0.0, 13.5), y\_range=(0.0, 4.2), aspect=(13.5, 4.2)); box\_w — a Polygon \[blue\] drawn in pipe (vertices=((0.3, 1.4), (2.5, 1.4), (2.5, 3.0), (0.3, 3.0)), fill\_opacity=0.18); lbl\_w — a Math \[blue\] that says "$w$" drawn in pipe; tag\_a — a Math \[blue\] that says "$upright("instance of ") A$" drawn in pipe; arrow\_f — an Arrow \[yellow\] labelled "f" drawn in pipe (start=(2.7, 2.2), end=(4.1, 2.2)); box\_fw — a Polygon \[green\] drawn in pipe (vertices=((4.3, 1.4), (6.7, 1.4), (6.7, 3.0), (4.3, 3.0)), fill\_opacity=0.18); lbl\_fw — a Math \[green\] that says "$f(w)$" drawn in pipe; tag\_b — a Math \[green\] that says "$upright("instance of ") B$" drawn in pipe; arrow\_in — an Arrow \[gray\] drawn in pipe (start=(6.9, 2.2), end=(7.9, 2.2)); box\_s — a Polygon \[yellow\] drawn in pipe (vertices=((8.1, 1.4), (10.9, 1.4), (10.9, 3.0), (8.1, 3.0)), fill\_opacity=0.18); lbl\_s — a Math \[yellow\] that says "$upright("solver for ") B$" drawn in pipe; arrow\_out — an Arrow \[gray\] drawn in pipe (start=(11.1, 2.2), end=(11.9, 2.2)); lbl\_ans — a Math \[text\] that says "$upright("yes / no")$" drawn in pipe; dir\_yes — a Math \[text\] that says "$B in upright("P") quad arrow.r.double quad A in upright("P")$"; head\_direction — a Heading that says "Which Way Hardness Travels" Actions: - [05:40.584](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=340.5835000000001): dir\_no is shown on the screen, written out. ##### [05:52.759](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=352.759) Narration: 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. Board: pipe — a Figure (x\_range=(0.0, 13.5), y\_range=(0.0, 4.2), aspect=(13.5, 4.2)); box\_w — a Polygon \[blue\] drawn in pipe (vertices=((0.3, 1.4), (2.5, 1.4), (2.5, 3.0), (0.3, 3.0)), fill\_opacity=0.18); lbl\_w — a Math \[blue\] that says "$w$" drawn in pipe; tag\_a — a Math \[blue\] that says "$upright("instance of ") A$" drawn in pipe; arrow\_f — an Arrow \[yellow\] labelled "f" drawn in pipe (start=(2.7, 2.2), end=(4.1, 2.2)); box\_fw — a Polygon \[green\] drawn in pipe (vertices=((4.3, 1.4), (6.7, 1.4), (6.7, 3.0), (4.3, 3.0)), fill\_opacity=0.18); lbl\_fw — a Math \[green\] that says "$f(w)$" drawn in pipe; tag\_b — a Math \[green\] that says "$upright("instance of ") B$" drawn in pipe; arrow\_in — an Arrow \[gray\] drawn in pipe (start=(6.9, 2.2), end=(7.9, 2.2)); box\_s — a Polygon \[yellow\] drawn in pipe (vertices=((8.1, 1.4), (10.9, 1.4), (10.9, 3.0), (8.1, 3.0)), fill\_opacity=0.18); lbl\_s — a Math \[yellow\] that says "$upright("solver for ") B$" drawn in pipe; arrow\_out — an Arrow \[gray\] drawn in pipe (start=(11.1, 2.2), end=(11.9, 2.2)); lbl\_ans — a Math \[text\] that says "$upright("yes / no")$" drawn in pipe; dir\_yes — a Math \[text\] that says "$B in upright("P") quad arrow.r.double quad A in upright("P")$"; dir\_no — a Math \[text\] that says "$A in.not upright("P") quad arrow.r.double quad B in.not upright("P")$"; head\_direction — a Heading that says "Which Way Hardness Travels" Actions: - [05:54.385](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=354.3845): travel is shown on the screen, written out. - [06:0.469](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=360.46850000000006): arrow\_f is indicated — a transient flash. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): dir\_no is hidden from the screen — left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): dir\_yes is hidden from the screen — left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): head\_direction is hidden from the screen — left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): pipe is hidden from the screen — left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): box\_w is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): lbl\_w is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): tag\_a is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): arrow\_f is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): box\_fw is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): lbl\_fw is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): tag\_b is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): arrow\_in is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): box\_s is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): lbl\_s is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): arrow\_out is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): lbl\_ans is hidden from the screen — pipe left the board. - [06:8.189](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=368.189): travel is hidden from the screen — left the board. ##### [06:9.389](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=369.389) Narration: 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. Board: Empty. Actions: - [06:9.389](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=369.389): head\_wrong is shown on the screen, written out. - [06:18.608](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=378.6075000000001): right\_way is shown on the screen, written out. - [06:19.107](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=379.10650000000004): right\_text is shown on the screen, written out. ##### [06:20.705](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=380.70500000000004) Narration: 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. Board: right\_way — a Math \[text\] that says "$upright("3SAT") \<=\_p B$"; right\_text — a Text \[text\] that says "Every 3SAT instance becomes a $B$ instance. A fast algorithm for $B$ would settle 3SAT, and with it all of NP. That is a lower bound on $B$."; head\_wrong — a Heading that says "The Direction Is the Proof" Actions: - [06:24.816](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=384.81550000000004): wrong\_way is shown on the screen, written out. - [06:32.164](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=392.16350000000006): wrong\_text is shown on the screen, written out. ##### [06:34.981](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=394.981) Narration: 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. Board: right\_way — a Math \[text\] that says "$upright("3SAT") \<=\_p B$"; right\_text — a Text \[text\] that says "Every 3SAT instance becomes a $B$ instance. A fast algorithm for $B$ would settle 3SAT, and with it all of NP. That is a lower bound on $B$."; wrong\_way — a Math \[text\] that says "$B \<=\_p upright("3SAT")$"; wrong\_text — a Text \[text\] that says "Every $B$ instance becomes a 3SAT instance. That bounds $B$ from above by a problem nobody can solve quickly, which says nothing about $B$ at all."; head\_wrong — a Heading that says "The Direction Is the Proof" Actions: - [06:41.472](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=401.47150000000005): right\_way is indicated — a transient flash. - [06:46.754](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=406.75350000000003): head\_wrong is hidden from the screen — left the board. - [06:46.754](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=406.75350000000003): right\_text is hidden from the screen — left the board. - [06:46.754](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=406.75350000000003): right\_way is hidden from the screen — left the board. - [06:46.754](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=406.75350000000003): wrong\_text is hidden from the screen — left the board. - [06:46.754](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=406.75350000000003): wrong\_way is hidden from the screen — left the board. ##### [06:47.954](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=407.9535) Narration: 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. Board: Empty. Actions: - [06:47.954](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=407.9535): head\_complete is shown on the screen, written out. - [06:52.714](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=412.71350000000007): hard\_math is shown on the screen, written out. - [06:57.823](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=417.82250000000005): hard\_panel is shown on the screen, written out. ##### [07:1.115](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=421.1155) Narration: 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. Board: hard\_math — a Math \[text\] that says "$forall L in upright("NP"): thin L \<=\_p B$"; hard\_panel — a Panel that says "$B$ is NP-hard when every problem in NP reduces to $B$ in polynomial time."; head\_complete — a Heading that says "NP-Hard and NP-Complete" Actions: - [07:6.225](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=426.22450000000003): complete\_panel is shown on the screen, written out. ##### [07:15.3](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=435.2995) Narration: 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. Board: hard\_math — a Math \[text\] that says "$forall L in upright("NP"): thin L \<=\_p B$"; hard\_panel — a Panel that says "$B$ is NP-hard when every problem in NP reduces to $B$ in polynomial time."; complete\_panel — a Panel that says "$B$ is NP-complete when $B$ is NP-hard and $B in upright("NP")$."; head\_complete — a Heading that says "NP-Hard and NP-Complete" Actions: - [07:21.918](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=441.9175): cook is shown on the screen, written out. ##### [07:32.792](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=452.79150000000004) Narration: 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. Board: hard\_math — a Math \[text\] that says "$forall L in upright("NP"): thin L \<=\_p B$"; hard\_panel — a Panel that says "$B$ is NP-hard when every problem in NP reduces to $B$ in polynomial time."; complete\_panel — a Panel that says "$B$ is NP-complete when $B$ is NP-hard and $B in upright("NP")$."; cook — a Panel that says "$upright("SAT")$ is NP-complete, and so is $upright("3SAT")$."; head\_complete — a Heading that says "NP-Hard and NP-Complete" Actions: - [07:44.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=464.68050000000005): chain is shown on the screen, written out. - [07:47.966](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=467.9655): chain (the "upright("3SAT")" part) is indicated — a transient flash. ##### [07:51.619](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=471.619) Narration: Which is exactly what we are going to do now, once, in full. Board: hard\_math — a Math \[text\] that says "$forall L in upright("NP"): thin L \<=\_p B$"; hard\_panel — a Panel that says "$B$ is NP-hard when every problem in NP reduces to $B$ in polynomial time."; complete\_panel — a Panel that says "$B$ is NP-complete when $B$ is NP-hard and $B in upright("NP")$."; cook — a Panel that says "$upright("SAT")$ is NP-complete, and so is $upright("3SAT")$."; chain — a Math \[text\] that says "$L \<=\_p upright("3SAT") \<=\_p B$"; head\_complete — a Heading that says "NP-Hard and NP-Complete" Actions: - [07:56.128](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=476.12779166666667): chain is hidden from the screen — left the board. - [07:56.128](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=476.12779166666667): complete\_panel is hidden from the screen — left the board. - [07:56.128](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=476.12779166666667): cook is hidden from the screen — left the board. - [07:56.128](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=476.12779166666667): hard\_math is hidden from the screen — left the board. - [07:56.128](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=476.12779166666667): hard\_panel is hidden from the screen — left the board. - [07:56.128](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=476.12779166666667): head\_complete is hidden from the screen — left the board. ### Scene 3: [Two Gadgets](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=477.16945833333335) Span: 07:57.169–11:21.002 (477.16945833333335s–681.0023541666667s). #### Objects - budget: a Math \[text\] that says "$k = n + 2m$" - cls\_claim: a Tex \[text\] that says "Every cover takes at least two vertices of this triangle." - cls\_read: a Tex \[text\] that says "So at most one vertex of the triangle is left outside." - cls\_tag: a Math \[green\] that says "$upright("clause gadget")$" drawn in gad - gad: a Figure (x\_range=(0.0, 9.2), y\_range=(0.0, 6.4), aspect=(9.2, 6.4)) - head\_3sat: a Heading that says "Three Satisfiability" - head\_clause: a Heading that says "One Triangle Per Clause" - head\_var: a Heading that says "One Edge Per Variable" - head\_wire: a Heading that says "The Wires and the Budget" - phi: a Math \[text\] that says "$phi = (x\_1 or x\_2 or overline(x)\_3) and (overline(x)\_1 or overline(x)\_2 or x\_3)$" - sat\_panel: a Panel that says "A 3SAT instance is a conjunction of clauses, each a disjunction of exactly three literals, where a literal is a variable or its negation. Is there an assignment making every clause true?" - t\_ab: a Line \[green\] drawn in gad (start=(6.4, 3.8), end=(5.0, 1.2)) - t\_bc: a Line \[green\] drawn in gad (start=(5.0, 1.2), end=(7.8, 1.2)) - t\_ca: a Line \[green\] drawn in gad (start=(7.8, 1.2), end=(6.4, 3.8)) - tb: a Point \[green\] labelled "overline(y)" drawn in gad (location=(5.0, 1.2), marker\_radius=0.13) - tc: a Point \[green\] labelled "z" drawn in gad (location=(7.8, 1.2), marker\_radius=0.13) - tight\_panel: a Panel that says "The variable gadgets force $n$ vertices and the clause gadgets force $2m$ more, and those vertices are all distinct. So $k = n + 2m$ is the smallest budget that could possibly work." - tt: a Point \[green\] labelled "x" drawn in gad (location=(6.4, 3.8), marker\_radius=0.13) - var\_claim: a Tex \[text\] that says "Every cover takes at least one endpoint of this edge." - var\_edge: a Line \[blue\] drawn in gad (start=(1.4, 5.0), end=(3.8, 5.0)) - var\_read: a Panel that says "If the cover takes the $x$ vertex, read $x$ as true. If it takes the $overline(x)$ vertex, read $x$ as false." - var\_tag: a Math \[blue\] that says "$upright("variable gadget")$" drawn in gad - vn: a Point \[blue\] labelled "overline(x)" drawn in gad (location=(3.8, 5.0), marker\_radius=0.13) - vx: a Point \[blue\] labelled "x" drawn in gad (location=(1.4, 5.0), marker\_radius=0.13) - wire: a Line \[gray\] drawn in gad (start=(1.4, 5.0), end=(6.4, 3.8)) - wire\_text: a Text \[text\] that says "For each literal in each clause, join that clause vertex to the gadget vertex carrying the same literal." #### Beats ##### [07:57.169](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=477.16945833333335) Narration: 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. Board: Empty. Actions: - [07:57.169](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=477.16945833333335): head\_3sat is shown on the screen, written out. - [08:2.103](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=482.1034583333334): sat\_panel is shown on the screen, written out. ##### [08:12.955](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=492.95545833333335) Narration: 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. Board: sat\_panel — a Panel that says "A 3SAT instance is a conjunction of clauses, each a disjunction of exactly three literals, where a literal is a variable or its negation. Is there an assignment making every clause true?"; head\_3sat — a Heading that says "Three Satisfiability" Actions: - [08:20.234](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=500.23445833333335): phi is shown on the screen, written out. ##### [08:24.224](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=504.22445833333336) Narration: 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. Board: phi — a Math \[text\] that says "$phi = (x\_1 or x\_2 or overline(x)\_3) and (overline(x)\_1 or overline(x)\_2 or x\_3)$"; sat\_panel — a Panel that says "A 3SAT instance is a conjunction of clauses, each a disjunction of exactly three literals, where a literal is a variable or its negation. Is there an assignment making every clause true?"; head\_3sat — a Heading that says "Three Satisfiability" Actions: - [08:27.208](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=507.20845833333334): phi (the "(x\_1 or x\_2 or overline(x)\_3)" part) is emphasized. - [08:31.272](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=511.27245833333336): phi (the "(overline(x)\_1 or overline(x)\_2 or x\_3)" part) is emphasized. - [08:31.272](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=511.27245833333336): phi (the "(x\_1 or x\_2 or overline(x)\_3)" part) is no longer emphasized. - [08:35.567](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=515.5674583333333): phi (the "(overline(x)\_1 or overline(x)\_2 or x\_3)" part) is no longer emphasized. ##### [08:40.928](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=520.9279583333333) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [08:54.302](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=534.3024583333333): head\_3sat is hidden from the screen — left the board. - [08:54.302](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=534.3024583333333): phi is hidden from the screen — left the board. - [08:54.302](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=534.3024583333333): sat\_panel is hidden from the screen — left the board. ##### [08:55.502](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=535.5024583333334) Narration: 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. Board: Empty. Actions: - [08:55.502](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=535.5024583333334): head\_var is shown on the screen, written out. - [08:55.502](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=535.5024583333334): gad is shown on the screen, written out. - [09:1.412](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=541.4124583333333): vx is shown on the screen, written out. - [09:1.662](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=541.6624583333333): vn is shown on the screen, written out. - [09:1.962](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=541.9624583333333): var\_edge is shown on the screen, drawn. - [09:2.362](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=542.3624583333334): var\_tag is shown on the screen, written out. ##### [09:7.307](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=547.3069583333333) Narration: 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. Board: gad — a Figure (x\_range=(0.0, 9.2), y\_range=(0.0, 6.4), aspect=(9.2, 6.4)); head\_var — a Heading that says "One Edge Per Variable"; vx — a Point \[blue\] labelled "x" drawn in gad (location=(1.4, 5.0), marker\_radius=0.13); vn — a Point \[blue\] labelled "overline(x)" drawn in gad (location=(3.8, 5.0), marker\_radius=0.13); var\_edge — a Line \[blue\] drawn in gad (start=(1.4, 5.0), end=(3.8, 5.0)); var\_tag — a Math \[blue\] that says "$upright("variable gadget")$" drawn in gad Actions: - [09:12.716](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=552.7164583333333): gad moves to a new place on the board. - [09:12.716](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=552.7164583333333): var\_claim is shown on the screen, written out. - [09:16.107](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=556.1074583333334): var\_edge is indicated — a transient flash. ##### [09:19.099](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=559.0989583333334) Narration: 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. Board: var\_claim — a Tex \[text\] that says "Every cover takes at least one endpoint of this edge."; gad — a Figure (x\_range=(0.0, 9.2), y\_range=(0.0, 6.4), aspect=(9.2, 6.4)); head\_var — a Heading that says "One Edge Per Variable"; vx — a Point \[blue\] labelled "x" drawn in gad (location=(1.4, 5.0), marker\_radius=0.13); vn — a Point \[blue\] labelled "overline(x)" drawn in gad (location=(3.8, 5.0), marker\_radius=0.13); var\_edge — a Line \[blue\] drawn in gad (start=(1.4, 5.0), end=(3.8, 5.0)); var\_tag — a Math \[blue\] that says "$upright("variable gadget")$" drawn in gad Actions: - [09:20.027](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=560.0274583333334): var\_read is shown on the screen, written out. - [09:27.957](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=567.9574583333333): vx is indicated — a transient flash. - [09:31.382](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=571.3824583333334): vn is indicated — a transient flash. - [09:34.25](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=574.2499583333333): head\_var is hidden from the screen — left the board. - [09:34.25](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=574.2499583333333): var\_claim is hidden from the screen — left the board. - [09:34.25](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=574.2499583333333): var\_read is hidden from the screen — left the board. ##### [09:34.85](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=574.8499583333333) Narration: 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. Board: gad — a Figure (x\_range=(0.0, 9.2), y\_range=(0.0, 6.4), aspect=(9.2, 6.4)); vx — a Point \[blue\] labelled "x" drawn in gad (location=(1.4, 5.0), marker\_radius=0.13); vn — a Point \[blue\] labelled "overline(x)" drawn in gad (location=(3.8, 5.0), marker\_radius=0.13); var\_edge — a Line \[blue\] drawn in gad (start=(1.4, 5.0), end=(3.8, 5.0)); var\_tag — a Math \[blue\] that says "$upright("variable gadget")$" drawn in gad Actions: - [09:34.85](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=574.8499583333333): head\_clause is shown on the screen, written out. - [09:41.13](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=581.1304583333333): tt is shown on the screen, written out. - [09:41.38](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=581.3804583333333): tb is shown on the screen, written out. - [09:41.63](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=581.6304583333333): tc is shown on the screen, written out. - [09:42.756](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=582.7564583333334): t\_ab is shown on the screen, drawn. - [09:43.006](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=583.0064583333334): t\_bc is shown on the screen, drawn. - [09:43.256](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=583.2564583333334): t\_ca is shown on the screen, drawn. - [09:43.656](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=583.6564583333334): cls\_tag is shown on the screen, written out. ##### [09:45.597](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=585.5969583333333) Narration: 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. Board: gad — a Figure (x\_range=(0.0, 9.2), y\_range=(0.0, 6.4), aspect=(9.2, 6.4)); vx — a Point \[blue\] labelled "x" drawn in gad (location=(1.4, 5.0), marker\_radius=0.13); vn — a Point \[blue\] labelled "overline(x)" drawn in gad (location=(3.8, 5.0), marker\_radius=0.13); var\_edge — a Line \[blue\] drawn in gad (start=(1.4, 5.0), end=(3.8, 5.0)); var\_tag — a Math \[blue\] that says "$upright("variable gadget")$" drawn in gad; head\_clause — a Heading that says "One Triangle Per Clause"; tt — a Point \[green\] labelled "x" drawn in gad (location=(6.4, 3.8), marker\_radius=0.13); tb — a Point \[green\] labelled "overline(y)" drawn in gad (location=(5.0, 1.2), marker\_radius=0.13); tc — a Point \[green\] labelled "z" drawn in gad (location=(7.8, 1.2), marker\_radius=0.13); t\_ab — a Line \[green\] drawn in gad (start=(6.4, 3.8), end=(5.0, 1.2)); t\_bc — a Line \[green\] drawn in gad (start=(5.0, 1.2), end=(7.8, 1.2)); t\_ca — a Line \[green\] drawn in gad (start=(7.8, 1.2), end=(6.4, 3.8)); cls\_tag — a Math \[green\] that says "$upright("clause gadget")$" drawn in gad Actions: - [09:51.564](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=591.5644583333334): tt is emphasized. - [09:54.048](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=594.0484583333333): The segment (5.0, 1.2) to (7.8, 1.2) in gad is lit up. ##### [09:59.072](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=599.0724583333333) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [09:59.072](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=599.0724583333333): tt is no longer emphasized. - [09:59.072](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=599.0724583333333): gad: retire a lit segment (unemphasize\_line). - [10:2.74](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=602.7404583333333): tb is emphasized. - [10:3.04](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=603.0404583333334): tc is emphasized. - [10:5.294](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=605.2944583333333): cls\_claim is shown on the screen, written out. - [10:7.652](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=607.6524583333334): cls\_read is shown on the screen, written out. - [10:14.757](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=614.7574583333334): cls\_claim is hidden from the screen — left the board. - [10:14.757](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=614.7574583333334): cls\_read is hidden from the screen — left the board. - [10:14.757](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=614.7574583333334): head\_clause is hidden from the screen — left the board. ##### [10:15.357](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=615.3574583333334) Narration: 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. Board: gad — a Figure (x\_range=(0.0, 9.2), y\_range=(0.0, 6.4), aspect=(9.2, 6.4)); vx — a Point \[blue\] labelled "x" drawn in gad (location=(1.4, 5.0), marker\_radius=0.13); vn — a Point \[blue\] labelled "overline(x)" drawn in gad (location=(3.8, 5.0), marker\_radius=0.13); var\_edge — a Line \[blue\] drawn in gad (start=(1.4, 5.0), end=(3.8, 5.0)); var\_tag — a Math \[blue\] that says "$upright("variable gadget")$" drawn in gad; tt — a Point \[green\] labelled "x" drawn in gad (location=(6.4, 3.8), marker\_radius=0.13); tb — a Point \[green\] labelled "overline(y)" drawn in gad (location=(5.0, 1.2), marker\_radius=0.13); tc — a Point \[green\] labelled "z" drawn in gad (location=(7.8, 1.2), marker\_radius=0.13); t\_ab — a Line \[green\] drawn in gad (start=(6.4, 3.8), end=(5.0, 1.2)); t\_bc — a Line \[green\] drawn in gad (start=(5.0, 1.2), end=(7.8, 1.2)); t\_ca — a Line \[green\] drawn in gad (start=(7.8, 1.2), end=(6.4, 3.8)); cls\_tag — a Math \[green\] that says "$upright("clause gadget")$" drawn in gad Actions: - [10:15.357](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=615.3574583333334): head\_wire is shown on the screen, written out. - [10:15.357](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=615.3574583333334): tb is no longer emphasized. - [10:15.357](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=615.3574583333334): tc is no longer emphasized. - [10:21.731](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=621.7314583333334): wire\_text is shown on the screen, written out. ##### [10:26.819](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=626.8189583333334) Narration: 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. Board: gad — a Figure (x\_range=(0.0, 9.2), y\_range=(0.0, 6.4), aspect=(9.2, 6.4)); vx — a Point \[blue\] labelled "x" drawn in gad (location=(1.4, 5.0), marker\_radius=0.13); vn — a Point \[blue\] labelled "overline(x)" drawn in gad (location=(3.8, 5.0), marker\_radius=0.13); var\_edge — a Line \[blue\] drawn in gad (start=(1.4, 5.0), end=(3.8, 5.0)); var\_tag — a Math \[blue\] that says "$upright("variable gadget")$" drawn in gad; tt — a Point \[green\] labelled "x" drawn in gad (location=(6.4, 3.8), marker\_radius=0.13); tb — a Point \[green\] labelled "overline(y)" drawn in gad (location=(5.0, 1.2), marker\_radius=0.13); tc — a Point \[green\] labelled "z" drawn in gad (location=(7.8, 1.2), marker\_radius=0.13); t\_ab — a Line \[green\] drawn in gad (start=(6.4, 3.8), end=(5.0, 1.2)); t\_bc — a Line \[green\] drawn in gad (start=(5.0, 1.2), end=(7.8, 1.2)); t\_ca — a Line \[green\] drawn in gad (start=(7.8, 1.2), end=(6.4, 3.8)); cls\_tag — a Math \[green\] that says "$upright("clause gadget")$" drawn in gad; wire\_text — a Text \[text\] that says "For each literal in each clause, join that clause vertex to the gadget vertex carrying the same literal."; head\_wire — a Heading that says "The Wires and the Budget" Actions: - [10:29.065](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=629.0654583333334): wire is shown on the screen, drawn. - [10:29.265](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=629.2654583333333): tt is indicated — a transient flash. - [10:30.365](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=630.3654583333333): vx is indicated — a transient flash. ##### [10:38.124](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=638.1239583333333) Narration: 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. Board: gad — a Figure (x\_range=(0.0, 9.2), y\_range=(0.0, 6.4), aspect=(9.2, 6.4)); vx — a Point \[blue\] labelled "x" drawn in gad (location=(1.4, 5.0), marker\_radius=0.13); vn — a Point \[blue\] labelled "overline(x)" drawn in gad (location=(3.8, 5.0), marker\_radius=0.13); var\_edge — a Line \[blue\] drawn in gad (start=(1.4, 5.0), end=(3.8, 5.0)); var\_tag — a Math \[blue\] that says "$upright("variable gadget")$" drawn in gad; tt — a Point \[green\] labelled "x" drawn in gad (location=(6.4, 3.8), marker\_radius=0.13); tb — a Point \[green\] labelled "overline(y)" drawn in gad (location=(5.0, 1.2), marker\_radius=0.13); tc — a Point \[green\] labelled "z" drawn in gad (location=(7.8, 1.2), marker\_radius=0.13); t\_ab — a Line \[green\] drawn in gad (start=(6.4, 3.8), end=(5.0, 1.2)); t\_bc — a Line \[green\] drawn in gad (start=(5.0, 1.2), end=(7.8, 1.2)); t\_ca — a Line \[green\] drawn in gad (start=(7.8, 1.2), end=(6.4, 3.8)); cls\_tag — a Math \[green\] that says "$upright("clause gadget")$" drawn in gad; wire\_text — a Text \[text\] that says "For each literal in each clause, join that clause vertex to the gadget vertex carrying the same literal."; head\_wire — a Heading that says "The Wires and the Budget"; wire — a Line \[gray\] drawn in gad (start=(1.4, 5.0), end=(6.4, 3.8)) Actions: - None. ##### [10:51.164](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=651.1639583333333) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [10:55.273](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=655.2734583333333): budget is shown on the screen, written out. ##### [11:4.685](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=664.6854583333334) Narration: 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. Board: gad — a Figure (x\_range=(0.0, 9.2), y\_range=(0.0, 6.4), aspect=(9.2, 6.4)); vx — a Point \[blue\] labelled "x" drawn in gad (location=(1.4, 5.0), marker\_radius=0.13); vn — a Point \[blue\] labelled "overline(x)" drawn in gad (location=(3.8, 5.0), marker\_radius=0.13); var\_edge — a Line \[blue\] drawn in gad (start=(1.4, 5.0), end=(3.8, 5.0)); var\_tag — a Math \[blue\] that says "$upright("variable gadget")$" drawn in gad; tt — a Point \[green\] labelled "x" drawn in gad (location=(6.4, 3.8), marker\_radius=0.13); tb — a Point \[green\] labelled "overline(y)" drawn in gad (location=(5.0, 1.2), marker\_radius=0.13); tc — a Point \[green\] labelled "z" drawn in gad (location=(7.8, 1.2), marker\_radius=0.13); t\_ab — a Line \[green\] drawn in gad (start=(6.4, 3.8), end=(5.0, 1.2)); t\_bc — a Line \[green\] drawn in gad (start=(5.0, 1.2), end=(7.8, 1.2)); t\_ca — a Line \[green\] drawn in gad (start=(7.8, 1.2), end=(6.4, 3.8)); cls\_tag — a Math \[green\] that says "$upright("clause gadget")$" drawn in gad; wire\_text — a Text \[text\] that says "For each literal in each clause, join that clause vertex to the gadget vertex carrying the same literal."; budget — a Math \[text\] that says "$k = n + 2m$"; head\_wire — a Heading that says "The Wires and the Budget"; wire — a Line \[gray\] drawn in gad (start=(1.4, 5.0), end=(6.4, 3.8)) Actions: - [11:6.159](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=666.1594583333334): tight\_panel is shown on the screen, written out. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): budget is hidden from the screen — left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): gad is hidden from the screen — left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): vx is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): vn is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): var\_edge is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): var\_tag is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): tt is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): tb is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): tc is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): t\_ab is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): t\_bc is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): t\_ca is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): cls\_tag is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): wire is hidden from the screen — gad left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): head\_wire is hidden from the screen — left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): tight\_panel is hidden from the screen — left the board. - [11:19.961](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=679.9606875000001): wire\_text is hidden from the screen — left the board. ### Scene 4: [One Formula, One Graph](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=681.0023541666667) Span: 11:21.002–18:27.959 (681.0023541666667s–1107.9585208333333s). #### Objects - G: a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)) - assign: a Table \[text\] that says "Variable Value $x\_1$ true $x\_2$ false $x\_3$ true" (rows=(('Variable', 'Value'), ('$x\_1$', 'true'), ('$x\_2$', 'false'), …, header=True) - back\_table: a Table \[text\] that says "Variable Value $x\_1$ false $x\_2$ true $x\_3$ false" (rows=(('Variable', 'Value'), ('$x\_1$', 'false'), ('$x\_2$', 'true'), …, header=True) - c1a: a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1) - c1b: a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1) - c1c: a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1) - c2a: a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1) - c2b: a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1) - c2c: a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1) - cover\_size: a Math \[text\] that says "$\|S\| = 3 + 4 = 7$" - edge\_list: a Block \[text\] that says "variable edges: one endpoint taken triangle edges: two of three taken wires: the risky case" - forced: a Block \[text\] that says "Exactly one endpoint of each variable edge is in $S$. Exactly two vertices of each triangle are in $S$. The excluded triangle vertex forces its literal true." - g\_n1: a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1) - g\_n2: a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1) - g\_n3: a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1) - g\_x1: a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1) - g\_x2: a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1) - g\_x3: a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1) - head\_back: a Heading that says "From a Cover to an Assignment" - head\_budget: a Heading that says "Why Seven Is the Only Budget" - head\_build: a Heading that says "The Graph This Formula Becomes" - head\_edges: a Heading that says "Every Edge Accounted For" - head\_forward: a Heading that says "From an Assignment to a Cover" - lower: an Arithmetic \[text\] that says "$3 times 1 = 3 2 times 2 = 4 k = 7$" (operator='+', operands=('3 times 1 = 3', '2 times 2 = 4'), result='k = 7') - phi: a Derivation \[text\] that says "$phi &= (x\_1 or x\_2 or overline(x)\_3) \\ &and (overline(x)\_1 or overline(x)\_2 or x\_3)$" - point: a Point \[yellow\] drawn in G (location=(1.2, 1.0)) - point\_2: a Point \[yellow\] drawn in G (location=(7.7, 3.2)) - point\_3: a Point \[yellow\] drawn in G (location=(1.2, 1.0)) - point\_4: a Point \[yellow\] drawn in G (location=(7.7, 3.2)) - point\_5: a Point \[yellow\] drawn in G (location=(2.4, 3.2)) - point\_6: a Point \[yellow\] drawn in G (location=(6.5, 1.0)) - size\_line: a Tex \[text\] that says "12 vertices, 15 edges, one pass over $phi$." - t1\_ab: a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)) - t1\_bc: a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)) - t1\_ca: a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)) - t2\_ab: a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)) - t2\_bc: a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)) - t2\_ca: a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)) - tight: a Panel that says "A cover of size 7 has no slack: exactly one endpoint of each variable edge, and exactly two vertices of each triangle." - ve1: a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)) - ve2: a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)) - ve3: a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)) - w1: a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)) - w2: a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)) - w3: a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)) - w4: a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)) - w5: a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)) - w6: a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)) #### Beats ##### [11:21.002](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=681.0023541666667) Narration: 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. Board: Empty. Actions: - [11:21.002](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=681.0023541666667): head\_build is shown on the screen, written out. - [11:21.002](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=681.0023541666667): G is shown on the screen, written out. - [11:21.002](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=681.0023541666667): phi is shown on the screen, written out. - [11:21.402](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=681.4023541666667): phi is shown on the screen, written out. - [11:27.759](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=687.7593541666666): g\_x1 is shown on the screen, written out. - [11:27.889](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=687.8893541666666): g\_n1 is shown on the screen, written out. - [11:28.019](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=688.0193541666667): g\_x2 is shown on the screen, written out. - [11:28.149](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=688.1493541666667): g\_n2 is shown on the screen, written out. - [11:28.279](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=688.2793541666667): g\_x3 is shown on the screen, written out. - [11:28.409](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=688.4093541666667): g\_n3 is shown on the screen, written out. - [11:29.094](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=689.0943541666667): ve1 is shown on the screen, drawn. - [11:29.294](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=689.2943541666667): ve2 is shown on the screen, drawn. - [11:29.494](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=689.4943541666667): ve3 is shown on the screen, drawn. ##### [11:33.503](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=693.5028541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); head\_build — a Heading that says "The Graph This Formula Becomes"; g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)) Actions: - [11:36.683](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=696.6833541666667): phi (the "(x\_1 or x\_2 or overline(x)\_3)" part) is emphasized. - [11:43.22](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=703.2203541666667): c1a is shown on the screen, written out. - [11:43.42](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=703.4203541666667): c1b is shown on the screen, written out. - [11:43.62](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=703.6203541666667): c1c is shown on the screen, written out. - [11:44.207](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=704.2073541666667): t1\_ab is shown on the screen, drawn. - [11:44.387](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=704.3873541666667): t1\_bc is shown on the screen, drawn. - [11:44.567](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=704.5673541666667): t1\_ca is shown on the screen, drawn. ##### [11:45.968](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=705.9678541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); head\_build — a Heading that says "The Graph This Formula Becomes"; g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)) Actions: - [11:45.968](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=705.9678541666667): phi (the "(x\_1 or x\_2 or overline(x)\_3)" part) is no longer emphasized. - [11:46.49](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=706.4903541666667): phi (the "(overline(x)\_1 or overline(x)\_2 or x\_3)" part) is emphasized. - [11:51.111](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=711.1113541666667): c2a is shown on the screen, written out. - [11:51.311](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=711.3113541666667): c2b is shown on the screen, written out. - [11:51.511](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=711.5113541666667): c2c is shown on the screen, written out. - [11:54.443](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=714.4433541666667): t2\_ab is shown on the screen, drawn. - [11:54.623](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=714.6233541666667): t2\_bc is shown on the screen, drawn. - [11:54.803](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=714.8033541666667): t2\_ca is shown on the screen, drawn. ##### [11:59.954](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=719.9543541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); head\_build — a Heading that says "The Graph This Formula Becomes"; g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)) Actions: - [11:59.954](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=719.9543541666667): phi (the "(overline(x)\_1 or overline(x)\_2 or x\_3)" part) is no longer emphasized. - [12:7.443](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=727.4433541666667): w1 is shown on the screen, drawn. - [12:10.589](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=730.5893541666667): w2 is shown on the screen, drawn. - [12:13.63](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=733.6303541666667): w3 is shown on the screen, drawn. ##### [12:15.485](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=735.4848541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); head\_build — a Heading that says "The Graph This Formula Becomes"; g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)) Actions: - [12:18.712](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=738.7123541666667): w4 is shown on the screen, drawn. - [12:19.559](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=739.5593541666667): w5 is shown on the screen, drawn. - [12:20.465](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=740.4653541666667): w6 is shown on the screen, drawn. ##### [12:26.638](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=746.6383541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); head\_build — a Heading that says "The Graph This Formula Becomes"; g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)) Actions: - [12:31.932](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=751.9323541666666): size\_line is shown on the screen, written out. - [12:42.869](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=762.8693541666667): head\_build is hidden from the screen — left the board. - [12:42.869](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=762.8693541666667): phi is hidden from the screen — left the board. - [12:42.869](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=762.8693541666667): size\_line is hidden from the screen — left the board. ##### [12:44.069](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=764.0693541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)) Actions: - [12:44.069](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=764.0693541666667): head\_budget is shown on the screen, written out. - [12:47.285](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=767.2853541666667): ve1 is emphasized. - [12:47.535](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=767.5353541666667): ve2 is emphasized. - [12:47.785](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=767.7853541666667): ve3 is emphasized. - [12:52.185](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=772.1853541666667): lower is shown on the screen, written out. ##### [12:54.306](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=774.3058541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)); head\_budget — a Heading that says "Why Seven Is the Only Budget" Actions: - [12:54.306](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=774.3058541666667): ve1 is no longer emphasized. - [12:54.306](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=774.3058541666667): ve2 is no longer emphasized. - [12:54.306](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=774.3058541666667): ve3 is no longer emphasized. - [12:55.269](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=775.2693541666666): t1\_ab is emphasized. - [12:55.269](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=775.2693541666666): t1\_bc is emphasized. - [12:55.269](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=775.2693541666666): t1\_ca is emphasized. - [12:55.269](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=775.2693541666666): t2\_ab is emphasized. - [12:55.269](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=775.2693541666666): t2\_bc is emphasized. - [12:55.269](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=775.2693541666666): t2\_ca is emphasized. - [12:59.333](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=779.3333541666667): lower is shown on the screen, written out. ##### [13:6.399](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=786.3993541666666) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [13:6.399](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=786.3993541666666): t1\_ab is no longer emphasized. - [13:6.399](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=786.3993541666666): t1\_bc is no longer emphasized. - [13:6.399](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=786.3993541666666): t1\_ca is no longer emphasized. - [13:6.399](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=786.3993541666666): t2\_ab is no longer emphasized. - [13:6.399](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=786.3993541666666): t2\_bc is no longer emphasized. - [13:6.399](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=786.3993541666666): t2\_ca is no longer emphasized. - [13:6.701](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=786.7013541666666): lower is shown on the screen, drawn. - [13:7.501](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=787.5013541666667): lower is shown on the screen, drawn. - [13:8.907](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=788.9073541666667): lower is shown on the screen, written out. ##### [13:18.783](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=798.7833541666666) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [13:22.487](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=802.4873541666667): tight is shown on the screen, written out. - [13:31.171](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=811.1713541666667): head\_budget is hidden from the screen — left the board. - [13:31.171](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=811.1713541666667): lower is hidden from the screen — left the board. - [13:31.171](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=811.1713541666667): tight is hidden from the screen — left the board. ##### [13:32.371](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=812.3713541666667) Narration: Take the formula's side first. Set x one true, x two false, and x three true. Check it against both clauses. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)) Actions: - [13:32.371](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=812.3713541666667): head\_forward is shown on the screen, written out. - [13:34.414](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=814.4143541666667): assign is shown on the screen, written out. - [13:34.714](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=814.7143541666667): assign is shown on the screen, written out. - [13:35.014](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=815.0143541666666): assign is shown on the screen, written out. - [13:35.314](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=815.3143541666667): assign is shown on the screen, written out. ##### [13:40.878](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=820.8778541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)); head\_forward — a Heading that says "From an Assignment to a Cover" Actions: - [13:45.777](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=825.7773541666667): assign (the "row=2" part) is indicated — a transient flash. - [13:54.275](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=834.2753541666666): assign (the "row=3" part) is indicated — a transient flash. ##### [14:0.488](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=840.4883541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [14:9.364](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=849.3643541666667): g\_x1 is emphasized. - [14:12.615](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=852.6153541666666): g\_n2 is emphasized. - [14:16.098](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=856.0983541666667): g\_x3 is emphasized. ##### [14:17.935](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=857.9348541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - None. ##### [14:29.13](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=869.1298541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [14:32.636](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=872.6363541666667): point is shown on the screen, grown. - [14:34.83](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=874.8303541666667): c1b is emphasized. - [14:35.136](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=875.1363541666667): point is hidden from the screen. - [14:35.18](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=875.1803541666667): c1c is emphasized. ##### [14:38.634](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=878.6343541666668) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [14:42.268](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=882.2683541666667): point\_2 is shown on the screen, grown. - [14:44.764](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=884.7643541666666): c2a is emphasized. - [14:44.768](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=884.7683541666667): point\_2 is hidden from the screen. - [14:45.114](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=885.1143541666667): c2c is emphasized. - [14:49.966](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=889.9663541666666): cover\_size is shown on the screen, written out. - [14:52.694](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=892.6943541666667): assign is hidden from the screen — left the board. - [14:52.694](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=892.6943541666667): cover\_size is hidden from the screen — left the board. - [14:52.694](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=892.6943541666667): head\_forward is hidden from the screen — left the board. ##### [14:53.294](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=893.2943541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)) Actions: - [14:53.294](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=893.2943541666667): head\_edges is shown on the screen, written out. - [14:59.25](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=899.2503541666667): edge\_list is shown on the screen, written out. ##### [15:2.694](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=902.6943541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)); edge\_list — a Block \[text\] that says "variable edges: one endpoint taken triangle edges: two of three taken wires: the risky case"; head\_edges — a Heading that says "Every Edge Accounted For" Actions: - [15:7.071](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=907.0713541666667): edge\_list (the "variable edges" part) is emphasized. - [15:8.673](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=908.6733541666667): ve1 is indicated — a transient flash. - [15:8.923](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=908.9233541666667): ve2 is indicated — a transient flash. - [15:9.173](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=909.1733541666667): ve3 is indicated — a transient flash. ##### [15:11.793](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=911.7928541666668) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [15:14.788](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=914.7883541666666): edge\_list (the "triangle edges" part) is emphasized. - [15:14.788](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=914.7883541666666): edge\_list (the "variable edges" part) is no longer emphasized. - [15:18.724](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=918.7243541666667): t1\_ab is indicated — a transient flash. - [15:18.724](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=918.7243541666667): t1\_bc is indicated — a transient flash. - [15:18.724](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=918.7243541666667): t1\_ca is indicated — a transient flash. - [15:18.724](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=918.7243541666667): t2\_ab is indicated — a transient flash. - [15:18.724](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=918.7243541666667): t2\_bc is indicated — a transient flash. - [15:18.724](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=918.7243541666667): t2\_ca is indicated — a transient flash. ##### [15:23.353](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=923.3528541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [15:24.908](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=924.9083541666666): edge\_list (the "triangle edges" part) is no longer emphasized. - [15:24.908](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=924.9083541666666): edge\_list (the "wires" part) is emphasized. - [15:32.861](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=932.8613541666667): point\_3 is shown on the screen, grown. - [15:35.861](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=935.8613541666667): point\_3 is hidden from the screen. - [15:36.161](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=936.1613541666667): point\_4 is shown on the screen, grown. ##### [15:36.886](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=936.8863541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)); edge\_list — a Block \[text\] that says "variable edges: one endpoint taken triangle edges: two of three taken wires: the risky case"; head\_edges — a Heading that says "Every Edge Accounted For"; point\_4 — a Point \[yellow\] drawn in G (location=(7.7, 3.2)) Actions: - [15:36.886](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=936.8863541666667): edge\_list (the "wires" part) is no longer emphasized. - [15:39.161](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=939.1613541666667): point\_4 is hidden from the screen. - [15:43.956](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=943.9563541666666): w1 is emphasized. - [15:46.929](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=946.9293541666667): g\_x1 is indicated — a transient flash. ##### [15:50.605](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=950.6053541666668) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)); edge\_list — a Block \[text\] that says "variable edges: one endpoint taken triangle edges: two of three taken wires: the risky case"; head\_edges — a Heading that says "Every Edge Accounted For" Actions: - [15:56.909](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=956.9093541666666): w5 is emphasized. - [15:59.301](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=959.3013541666667): g\_n2 is indicated — a transient flash. ##### [16:6.066](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=966.0658541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [16:20.009](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=980.0093541666666): w1 is no longer emphasized. - [16:20.009](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=980.0093541666666): w5 is no longer emphasized. - [16:22.947](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=982.9468541666668): edge\_list is hidden from the screen — left the board. - [16:22.947](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=982.9468541666668): head\_edges is hidden from the screen — left the board. ##### [16:24.147](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=984.1468541666668) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)) Actions: - [16:24.147](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=984.1468541666668): head\_back is shown on the screen, written out. - [16:24.147](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=984.1468541666668): g\_x1 is no longer emphasized. - [16:24.147](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=984.1468541666668): g\_n2 is no longer emphasized. - [16:24.147](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=984.1468541666668): g\_x3 is no longer emphasized. - [16:24.147](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=984.1468541666668): c1b is no longer emphasized. - [16:24.147](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=984.1468541666668): c2a is no longer emphasized. - [16:29.301](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=989.3013541666667): g\_n1 is emphasized. - [16:29.551](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=989.5513541666667): g\_x2 is emphasized. - [16:29.801](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=989.8013541666667): g\_n3 is emphasized. - [16:30.051](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=990.0513541666667): c1a is emphasized. - [16:30.301](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=990.3013541666667): c2b is emphasized. ##### [16:36.867](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=996.8668541666667) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)); head\_back — a Heading that says "From a Cover to an Assignment" Actions: - [16:37.389](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=997.3893541666666): forced is shown on the screen, written out. - [16:45.643](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1005.6433541666667): forced (the "one endpoint of each variable edge" part) is emphasized. - [16:49.161](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1009.1613541666667): forced (the "one endpoint of each variable edge" part) is no longer emphasized. - [16:49.161](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1009.1613541666667): forced (the "two vertices of each triangle" part) is emphasized. ##### [16:50.609](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1010.6088541666668) Narration: 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. Board: G — a Figure (x\_range=(0.2, 9.9), y\_range=(0.2, 7.1), aspect=(9.7, 6.9)); g\_x1 — a Point \[blue\] labelled "x\_1" drawn in G (location=(0.9, 6.3), marker\_radius=0.1); g\_n1 — a Point \[blue\] labelled "overline(x)\_1" drawn in G (location=(2.6, 6.3), marker\_radius=0.1); g\_x2 — a Point \[blue\] labelled "x\_2" drawn in G (location=(4.2, 6.3), marker\_radius=0.1); g\_n2 — a Point \[blue\] labelled "overline(x)\_2" drawn in G (location=(5.9, 6.3), marker\_radius=0.1); g\_x3 — a Point \[blue\] labelled "x\_3" drawn in G (location=(7.5, 6.3), marker\_radius=0.1); g\_n3 — a Point \[blue\] labelled "overline(x)\_3" drawn in G (location=(9.2, 6.3), marker\_radius=0.1); ve1 — a Line \[blue\] drawn in G (start=(0.9, 6.3), end=(2.6, 6.3)); ve2 — a Line \[blue\] drawn in G (start=(4.2, 6.3), end=(5.9, 6.3)); ve3 — a Line \[blue\] drawn in G (start=(7.5, 6.3), end=(9.2, 6.3)); c1a — a Point \[green\] labelled "x\_1" drawn in G (location=(1.2, 1.0), marker\_radius=0.1); c1b — a Point \[green\] labelled "x\_2" drawn in G (location=(2.4, 3.2), marker\_radius=0.1); c1c — a Point \[green\] labelled "overline(x)\_3" drawn in G (location=(3.6, 1.0), marker\_radius=0.1); t1\_ab — a Line \[green\] drawn in G (start=(1.2, 1.0), end=(2.4, 3.2)); t1\_bc — a Line \[green\] drawn in G (start=(2.4, 3.2), end=(3.6, 1.0)); t1\_ca — a Line \[green\] drawn in G (start=(3.6, 1.0), end=(1.2, 1.0)); c2a — a Point \[green\] labelled "overline(x)\_1" drawn in G (location=(6.5, 1.0), marker\_radius=0.1); c2b — a Point \[green\] labelled "overline(x)\_2" drawn in G (location=(7.7, 3.2), marker\_radius=0.1); c2c — a Point \[green\] labelled "x\_3" drawn in G (location=(8.9, 1.0), marker\_radius=0.1); t2\_ab — a Line \[green\] drawn in G (start=(6.5, 1.0), end=(7.7, 3.2)); t2\_bc — a Line \[green\] drawn in G (start=(7.7, 3.2), end=(8.9, 1.0)); t2\_ca — a Line \[green\] drawn in G (start=(8.9, 1.0), end=(6.5, 1.0)); w1 — a Line \[gray\] drawn in G (start=(1.2, 1.0), end=(0.9, 6.3)); w2 — a Line \[gray\] drawn in G (start=(2.4, 3.2), end=(4.2, 6.3)); w3 — a Line \[gray\] drawn in G (start=(3.6, 1.0), end=(9.2, 6.3)); w4 — a Line \[gray\] drawn in G (start=(6.5, 1.0), end=(2.6, 6.3)); w5 — a Line \[gray\] drawn in G (start=(7.7, 3.2), end=(5.9, 6.3)); w6 — a Line \[gray\] drawn in G (start=(8.9, 1.0), end=(7.5, 6.3)); forced — a Block \[text\] that says "Exactly one endpoint of each variable edge is in $S$. Exactly two vertices of each triangle are in $S$. The excluded triangle vertex forces its literal true."; head\_back — a Heading that says "From a Cover to an Assignment" Actions: - [16:51.015](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1011.0153541666666): back\_table is shown on the screen, written out. - [16:56.077](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1016.0773541666666): back\_table is shown on the screen, written out. - [16:56.077](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1016.0773541666666): g\_n1 is indicated — a transient flash. - [16:59.003](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1019.0033541666667): back\_table is shown on the screen, written out. - [16:59.003](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1019.0033541666667): g\_x2 is indicated — a transient flash. - [17:1.848](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1021.8483541666667): back\_table is shown on the screen, written out. - [17:1.848](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1021.8483541666667): g\_n3 is indicated — a transient flash. ##### [17:7.986](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1027.9858541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [17:12.815](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1032.8153541666666): forced (the "excluded triangle vertex" part) is emphasized. - [17:12.815](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1032.8153541666666): forced (the "two vertices of each triangle" part) is no longer emphasized. - [17:18.945](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1038.9453541666667): point\_5 is shown on the screen, grown. - [17:21.945](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1041.9453541666667): point\_5 is hidden from the screen. ##### [17:22.262](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1042.2623541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [17:23.528](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1043.5283541666668): w2 is emphasized. - [17:33.28](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1053.2803541666667): g\_x2 is indicated — a transient flash. ##### [17:38.583](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1058.5828541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [17:48.671](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1068.6713541666668): t1\_ab is indicated — a transient flash. - [17:48.671](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1068.6713541666668): t1\_bc is indicated — a transient flash. - [17:48.671](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1068.6713541666668): t1\_ca is indicated — a transient flash. ##### [17:55.378](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1075.3783541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [17:55.378](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1075.3783541666667): w2 is no longer emphasized. - [17:58.664](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1078.6643541666667): point\_6 is shown on the screen, grown. - [18:1.664](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1081.6643541666667): point\_6 is hidden from the screen. - [18:1.729](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1081.7293541666668): w4 is emphasized. - [18:5.63](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1085.6303541666666): g\_n1 is indicated — a transient flash. - [18:8.881](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1088.8813541666668): t2\_ab is indicated — a transient flash. - [18:8.881](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1088.8813541666668): t2\_bc is indicated — a transient flash. - [18:8.881](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1088.8813541666668): t2\_ca is indicated — a transient flash. ##### [18:12.743](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1092.7433541666667) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [18:12.743](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1092.7433541666667): w4 is no longer emphasized. - [18:12.743](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1092.7433541666667): forced (the "excluded triangle vertex" part) is no longer emphasized. - [18:18.838](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1098.8383541666667): back\_table (the "column=2" part) is indicated — a transient flash. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): G is hidden from the screen — left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): g\_x1 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): g\_n1 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): g\_x2 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): g\_n2 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): g\_x3 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): g\_n3 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): ve1 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): ve2 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): ve3 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): c1a is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): c1b is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): c1c is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): t1\_ab is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): t1\_bc is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): t1\_ca is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): c2a is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): c2b is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): c2c is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): t2\_ab is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): t2\_bc is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): t2\_ca is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): w1 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): w2 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): w3 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): w4 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): w5 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): w6 is hidden from the screen — G left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): back\_table is hidden from the screen — left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): forced is hidden from the screen — left the board. - [18:26.917](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1106.9168541666668): head\_back is hidden from the screen — left the board. ### Scene 5: [What Was Proved](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1107.9585208333333) Span: 18:27.959–21:1.901 (1107.9585208333333s–1261.9007916666667s). #### Objects - a1: a Vector \[gray\] drawn in web (start=(2.4, 4.5), end=(5.2, 3.1), trim\_tip=True) - a2: a Vector \[gray\] drawn in web (start=(2.4, 3.1), end=(5.2, 3.1), trim\_tip=True) - a3: a Vector \[gray\] drawn in web (start=(2.4, 1.7), end=(5.2, 3.1), trim\_tip=True) - a4: a Vector \[yellow\] drawn in web (start=(5.2, 3.1), end=(7.4, 3.1), trim\_tip=True) - a5: a Vector \[red\] labelled "upright("this lecture")" drawn in web (start=(7.4, 3.1), end=(9.6, 3.1), trim\_tip=True) - complete\_math: a Math \[text\] that says "$upright("VC") upright(" is NP-complete")$" - head\_moral: a Heading that says "What the Claim Is About" - head\_web: a Heading that says "Where Vertex Cover Now Sits" - l1: a Point \[gray\] labelled "L\_1" drawn in web (location=(2.4, 4.5), marker\_radius=0.11) - l2: a Point \[gray\] labelled "L\_2" drawn in web (location=(2.4, 3.1), marker\_radius=0.11) - l3: a Point \[gray\] labelled "L\_3" drawn in web (location=(2.4, 1.7), marker\_radius=0.11) - meaning: a Math \[text\] that says "$upright("VC") in upright("P") quad arrow.r.double quad upright("P") = upright("NP")$" - moral: a Panel that says "NP-hardness is proved about a problem by exhibiting a reduction. It is a theorem on a page. It holds whoever is looking at the problem, and whatever they have already tried." - np\_tag: a Math \[gray\] that says "$upright("NP")$" drawn in web - reduce\_math: a Math \[text\] that says "$upright("3SAT") \<=\_p upright("VC")$" - region: a Polygon \[gray\] drawn in web (vertices=((0.4, 0.7), (10.6, 0.7), (10.6, 5.6), (0.4, 5.6)), fill\_opacity=0.1) - sat: a Point \[blue\] labelled "upright("SAT")" drawn in web (location=(5.2, 3.1), marker\_radius=0.14) - tsat: a Point \[blue\] labelled "upright("3SAT")" drawn in web (location=(7.4, 3.1), marker\_radius=0.14) - vcp: a Point \[red\] labelled "upright("VC")" drawn in web (location=(9.6, 3.1), marker\_radius=0.16) - web: a Figure (x\_range=(0.0, 11.0), y\_range=(0.0, 6.6), aspect=(11.0, 6.6)) #### Beats ##### [18:27.959](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1107.9585208333333) Narration: 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. Board: Empty. Actions: - [18:27.959](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1107.9585208333333): head\_web is shown on the screen, written out. - [18:27.959](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1107.9585208333333): web is shown on the screen, written out. - [18:31.396](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1111.3955208333332): region is shown on the screen, written out. - [18:31.596](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1111.5955208333332): np\_tag is shown on the screen, written out. ##### [18:41.005](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1121.0045208333333) Narration: 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. Board: web — a Figure (x\_range=(0.0, 11.0), y\_range=(0.0, 6.6), aspect=(11.0, 6.6)); head\_web — a Heading that says "Where Vertex Cover Now Sits"; region — a Polygon \[gray\] drawn in web (vertices=((0.4, 0.7), (10.6, 0.7), (10.6, 5.6), (0.4, 5.6)), fill\_opacity=0.1); np\_tag — a Math \[gray\] that says "$upright("NP")$" drawn in web Actions: - [18:43.768](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1123.7675208333333): tsat is shown on the screen, written out. - [18:45.986](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1125.9855208333333): vcp is shown on the screen, written out. - [18:50.026](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1130.0255208333333): reduce\_math is shown on the screen, written out. - [18:51.826](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1131.8255208333333): a5 is shown on the screen, drawn. ##### [18:54.352](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1134.3520208333332) Narration: 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. Board: web — a Figure (x\_range=(0.0, 11.0), y\_range=(0.0, 6.6), aspect=(11.0, 6.6)); reduce\_math — a Math \[text\] that says "$upright("3SAT") \<=\_p upright("VC")$"; head\_web — a Heading that says "Where Vertex Cover Now Sits"; region — a Polygon \[gray\] drawn in web (vertices=((0.4, 0.7), (10.6, 0.7), (10.6, 5.6), (0.4, 5.6)), fill\_opacity=0.1); np\_tag — a Math \[gray\] that says "$upright("NP")$" drawn in web; tsat — a Point \[blue\] labelled "upright("3SAT")" drawn in web (location=(7.4, 3.1), marker\_radius=0.14); vcp — a Point \[red\] labelled "upright("VC")" drawn in web (location=(9.6, 3.1), marker\_radius=0.16); a5 — a Vector \[red\] labelled "upright("this lecture")" drawn in web (start=(7.4, 3.1), end=(9.6, 3.1), trim\_tip=True) Actions: - [19:3.084](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1143.0835208333333): sat is shown on the screen, written out. - [19:6.334](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1146.3335208333333): l1 is shown on the screen, written out. - [19:6.534](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1146.5335208333333): l2 is shown on the screen, written out. - [19:6.734](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1146.7335208333334): l3 is shown on the screen, written out. - [19:7.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1147.6805208333333): a1 is shown on the screen, drawn. - [19:7.931](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1147.9305208333333): a2 is shown on the screen, drawn. - [19:8.181](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1148.1805208333333): a3 is shown on the screen, drawn. ##### [19:9.674](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1149.6740208333333) Narration: 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. Board: web — a Figure (x\_range=(0.0, 11.0), y\_range=(0.0, 6.6), aspect=(11.0, 6.6)); reduce\_math — a Math \[text\] that says "$upright("3SAT") \<=\_p upright("VC")$"; head\_web — a Heading that says "Where Vertex Cover Now Sits"; region — a Polygon \[gray\] drawn in web (vertices=((0.4, 0.7), (10.6, 0.7), (10.6, 5.6), (0.4, 5.6)), fill\_opacity=0.1); np\_tag — a Math \[gray\] that says "$upright("NP")$" drawn in web; tsat — a Point \[blue\] labelled "upright("3SAT")" drawn in web (location=(7.4, 3.1), marker\_radius=0.14); vcp — a Point \[red\] labelled "upright("VC")" drawn in web (location=(9.6, 3.1), marker\_radius=0.16); a5 — a Vector \[red\] labelled "upright("this lecture")" drawn in web (start=(7.4, 3.1), end=(9.6, 3.1), trim\_tip=True); sat — a Point \[blue\] labelled "upright("SAT")" drawn in web (location=(5.2, 3.1), marker\_radius=0.14); l1 — a Point \[gray\] labelled "L\_1" drawn in web (location=(2.4, 4.5), marker\_radius=0.11); l2 — a Point \[gray\] labelled "L\_2" drawn in web (location=(2.4, 3.1), marker\_radius=0.11); l3 — a Point \[gray\] labelled "L\_3" drawn in web (location=(2.4, 1.7), marker\_radius=0.11); a1 — a Vector \[gray\] drawn in web (start=(2.4, 4.5), end=(5.2, 3.1), trim\_tip=True); a2 — a Vector \[gray\] drawn in web (start=(2.4, 3.1), end=(5.2, 3.1), trim\_tip=True); a3 — a Vector \[gray\] drawn in web (start=(2.4, 1.7), end=(5.2, 3.1), trim\_tip=True) Actions: - [19:11.033](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1151.0325208333334): a4 is shown on the screen, drawn. - [19:15.909](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1155.9085208333333): a5 is indicated — a transient flash. ##### [19:24.996](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1164.9955208333333) Narration: 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. Board: web — a Figure (x\_range=(0.0, 11.0), y\_range=(0.0, 6.6), aspect=(11.0, 6.6)); reduce\_math — a Math \[text\] that says "$upright("3SAT") \<=\_p upright("VC")$"; head\_web — a Heading that says "Where Vertex Cover Now Sits"; region — a Polygon \[gray\] drawn in web (vertices=((0.4, 0.7), (10.6, 0.7), (10.6, 5.6), (0.4, 5.6)), fill\_opacity=0.1); np\_tag — a Math \[gray\] that says "$upright("NP")$" drawn in web; tsat — a Point \[blue\] labelled "upright("3SAT")" drawn in web (location=(7.4, 3.1), marker\_radius=0.14); vcp — a Point \[red\] labelled "upright("VC")" drawn in web (location=(9.6, 3.1), marker\_radius=0.16); a5 — a Vector \[red\] labelled "upright("this lecture")" drawn in web (start=(7.4, 3.1), end=(9.6, 3.1), trim\_tip=True); sat — a Point \[blue\] labelled "upright("SAT")" drawn in web (location=(5.2, 3.1), marker\_radius=0.14); l1 — a Point \[gray\] labelled "L\_1" drawn in web (location=(2.4, 4.5), marker\_radius=0.11); l2 — a Point \[gray\] labelled "L\_2" drawn in web (location=(2.4, 3.1), marker\_radius=0.11); l3 — a Point \[gray\] labelled "L\_3" drawn in web (location=(2.4, 1.7), marker\_radius=0.11); a1 — a Vector \[gray\] drawn in web (start=(2.4, 4.5), end=(5.2, 3.1), trim\_tip=True); a2 — a Vector \[gray\] drawn in web (start=(2.4, 3.1), end=(5.2, 3.1), trim\_tip=True); a3 — a Vector \[gray\] drawn in web (start=(2.4, 1.7), end=(5.2, 3.1), trim\_tip=True); a4 — a Vector \[yellow\] drawn in web (start=(5.2, 3.1), end=(7.4, 3.1), trim\_tip=True) Actions: - [19:38.649](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1178.6485208333334): complete\_math is shown on the screen, written out. - [19:38.849](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1178.8485208333334): vcp is indicated — a transient flash. ##### [19:40.473](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1180.4730208333333) Narration: 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. Board: web — a Figure (x\_range=(0.0, 11.0), y\_range=(0.0, 6.6), aspect=(11.0, 6.6)); reduce\_math — a Math \[text\] that says "$upright("3SAT") \<=\_p upright("VC")$"; complete\_math — a Math \[text\] that says "$upright("VC") upright(" is NP-complete")$"; head\_web — a Heading that says "Where Vertex Cover Now Sits"; region — a Polygon \[gray\] drawn in web (vertices=((0.4, 0.7), (10.6, 0.7), (10.6, 5.6), (0.4, 5.6)), fill\_opacity=0.1); np\_tag — a Math \[gray\] that says "$upright("NP")$" drawn in web; tsat — a Point \[blue\] labelled "upright("3SAT")" drawn in web (location=(7.4, 3.1), marker\_radius=0.14); vcp — a Point \[red\] labelled "upright("VC")" drawn in web (location=(9.6, 3.1), marker\_radius=0.16); a5 — a Vector \[red\] labelled "upright("this lecture")" drawn in web (start=(7.4, 3.1), end=(9.6, 3.1), trim\_tip=True); sat — a Point \[blue\] labelled "upright("SAT")" drawn in web (location=(5.2, 3.1), marker\_radius=0.14); l1 — a Point \[gray\] labelled "L\_1" drawn in web (location=(2.4, 4.5), marker\_radius=0.11); l2 — a Point \[gray\] labelled "L\_2" drawn in web (location=(2.4, 3.1), marker\_radius=0.11); l3 — a Point \[gray\] labelled "L\_3" drawn in web (location=(2.4, 1.7), marker\_radius=0.11); a1 — a Vector \[gray\] drawn in web (start=(2.4, 4.5), end=(5.2, 3.1), trim\_tip=True); a2 — a Vector \[gray\] drawn in web (start=(2.4, 3.1), end=(5.2, 3.1), trim\_tip=True); a3 — a Vector \[gray\] drawn in web (start=(2.4, 1.7), end=(5.2, 3.1), trim\_tip=True); a4 — a Vector \[yellow\] drawn in web (start=(5.2, 3.1), end=(7.4, 3.1), trim\_tip=True) Actions: - [19:46.18](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1186.1795208333333): a4 is indicated — a transient flash. - [19:46.48](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1186.4795208333333): a5 is indicated — a transient flash. ##### [19:51.308](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1191.3080208333333) Narration: 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. Board: Unchanged from the preceding beat in this scene. Actions: - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): complete\_math is hidden from the screen — left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): head\_web is hidden from the screen — left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): reduce\_math is hidden from the screen — left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): web is hidden from the screen — left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): region is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): np\_tag is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): tsat is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): vcp is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): a5 is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): sat is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): l1 is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): l2 is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): l3 is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): a1 is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): a2 is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): a3 is hidden from the screen — web left the board. - [20:5.681](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1205.6810208333334): a4 is hidden from the screen — web left the board. ##### [20:6.881](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1206.8810208333332) Narration: 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. Board: Empty. Actions: - [20:6.881](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1206.8810208333332): head\_moral is shown on the screen, written out. ##### [20:21.866](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1221.8660208333333) Narration: 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. Board: head\_moral — a Heading that says "What the Claim Is About" Actions: - [20:33.674](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1233.6735208333332): meaning is shown on the screen, written out. - [20:37.748](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1237.7475208333333): A box is drawn around meaning. ##### [20:39.289](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1239.2885208333332) Narration: 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. Board: meaning — a Math \[text\] that says "$upright("VC") in upright("P") quad arrow.r.double quad upright("P") = upright("NP")$"; head\_moral — a Heading that says "What the Claim Is About" Actions: - [20:44.212](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1244.2115208333332): moral is shown on the screen, written out. ##### [20:55.945](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1255.9450208333333) Narration: It says nothing whatsoever about you. It says where the problem stands. Board: meaning — a Math \[text\] that says "$upright("VC") in upright("P") quad arrow.r.double quad upright("P") = upright("NP")$"; moral — a Panel that says "NP-hardness is proved about a problem by exhibiting a reduction. It is a theorem on a page. It holds whoever is looking at the problem, and whatever they have already tried."; head\_moral — a Heading that says "What the Claim Is About" Actions: - [20:59.812](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1259.8115208333334): moral (the "a theorem on a page" part) is indicated — a transient flash. - [21:0.859](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1260.859125): head\_moral is hidden from the screen — left the board. - [21:0.859](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1260.859125): meaning is hidden from the screen — left the board. - [21:0.859](https://academa.ai/lectures/three-sat-vertex-cover-reduction?t=1260.859125): moral is hidden from the screen — left the board.