Video 2-7: Example NP-completeness prooof (overview)

0:04 Let's try to squeeze one reduction into the last few minutes. Okay, it's spelled out in detail on the slides. Um, but let me give you the gist of it. A more typical example of a reduction, the one that we'll look at uh relates this problem three, which is a boolean formula where um everything looks like this. It's a big and And what is in the end parts is an or of variables or negated variables. So all the inputs look like this plus each of these clauses have have at most three literal in them. So literal is this thing a variable or the negation of a variable and a clause is the or of three such things of three

1:02 literals and you can show that this is nplete um some of you will look at that and the second problem that we reduce to is uh vertex cover that's what I asked about initially vertex cover on the example you're given a graph and you try to select some vertices so that all the edges in the graph have one end point selected. So you could always pick all the vertices and satisfy this but the goal is to find a small subset of the vertices and the decision version has a threshold. So you're not allowed to pick more than K vertices and you want to satisfy the condition that every edge is has one endpoint selected. For example, here a smallest vertex cover uses these uses three vertices. Then all these edges have at least one endpoint selected. It's fine to have both end points selected and you cannot do it with just two vertices u in this case by just uh trying all

2:09 options and uh the the full proof should show that vertex cover is nplete that consists of two parts showing that it is in NP and that it is NP heart and let's only sketch the NP heart

2:27 the intuition that you should follow and that's what you do in your reductions too. You take the new problem vertex cover and suppose that that is solvable and now you take an instance of the old problem that's known to be np heart and you cast it in the language of this new problem. So we express a three set instance a formula as a graph so that the vertex cover of this graph says something about whether or not this formula can be satisfied. Okay. And here's the formal construction. I only have time for the example. Uh here's a formula. It has these clauses. For each clause you make a little triangle and it's connected by these blue edges. and the uh vertices are labeled by the literals in the clause. That by itself wouldn't be interesting, but you add green edges between every two literals in different clauses that contradict each other. So here I have x1 and not x1. I cannot have both at the same time. Put an edge between them. And you do this for all all pairs of literals. if they are a variable and the negation of the same variable, put an edge between them in green. And then the key observation is that um if that formula is satisfiable, it means there's a way to set the

3:47 variables so that in each of those cases, one of the three at least is true. And then you can you can pick the true thing and make that not part of the vertex cover, but take all the other vertices. So uh here you would you would read off an assignment of the variables that satisfies the formula by setting x1 to false, x3 to false, x1 to false again, okay, and x4 to true. And that should satisfy this formula. Now the the thing is if there's a way to pick from each triangle two vertices such that all the green edges are covered then you exactly satisfy the formula and that's an if and only if uh it goes both ways. Um the full proof in all details is spelled out on the slides. So if you haven't seen this example before you can you can read it there. I hope it's is actually uh clear enough even without my voice over.