Construction – Intro to Theoretical Computer Science

Construction – Intro to Theoretical Computer Science


So let’s say we are starting out and I’m going to do is using an example. So let’s say we start up with the following Boolean formula (x₁ or not-x₂ or x₃) and (not-x₁ or x₂) and ( not-x₂ or x₃) and the array we’re going to transform this into a network is we’re going to do groups of vertices for each clause. So for this clause here, for this one here, and for this one here. So, this is our first group of vertices and we’re going to have one vertex for each variable in that clause. So, this vertex here is for the x₁. This vertex here is for the not-x₂. This one here is for the x₃. For this one here, we’re going to do another group. This one here is for the not-x₁. This one here is for the x₂. And for that clause done here. We’re going to do the same thing. So we have not-x₂ and here we have x₃. And now, we’re going to draw a lot of edges. So from each vertex, we’re going to draw edges to every vertex in the other groups with one exception. We’re not going to draw an edge if we have the same variable, but 1 is the untouched variable and the other one has a not. So x₁ and x₂, we’re going to draw an edge. x₁ and x₃, we’re going to do an edge.. And x₁ and not-x₂ also but we’re not going to do an edge here. And it works similarly for this one here. So not-x₂, not-x₁, that’s something we don’t care about. That’s something where we draw an edge. no-x₂ and x₂. And then we have a not. Here, we do not have a not. So we don’t draw an edge. And down here, that’s fine. And here we have a case where we have not-x₂ and not-x₂. That’s also fine. So we’ll draw an edge here. It’s early if we have a not and then here we don’t have one. So for x₃, we can draw an edge down here. Down here. Again, those are the same. So we do draw an edge. That’s fine and we’re draw here. Now let’s look at those here. So we already have all the edges all to these groups. So we only need to look down here and then the graph edges here and the same thing is going to happen here. So x₂, I’m not drawing an edge to this not-x₂ here and we’re drawing an edge down here. And we’ve already drawn all the edges down here. So this is the network that we constructed. Now what about the size of the graph? So if the Boolean formula here has polynomial size, so we have n variables or in this case three variables and we said that we’re going to have the total length of the Boolean formula. The polynomial and the number of variables. So, if this length here is polynomial, then the network also will have polynomial size because we have one vertex for each of the variables that occur here, so the size really doesn’t change that much. We introduced edges but you already know that the number of edges is quadratic in the number of vertices that we have. So, the size stays polynomial which is already good for our reduction. But now I still need to show you what satisfiability has to do with clique. We’re actually going to do this as a quiz. So let’s say that the Boolean formula has m clauses. So in this case, m is 3 but you can consider the more general case here and then let’s say that the graph that we have constructed has a clique of size m. So one clique of size m, for example here, because m is 3 would be this here. All vertices are connected to each other. There’s others that you can find actually. So, if she can’t find a clique of size m in a graph that was constructed this way, does that graph contain at least one vertex from each clause group and by clause group, I mean, the groups of vertices that we introduced for each of the clauses from our satisfiability formula. And what I would also like you to think about is if a clique can contain multiple vertices from one of this clause groups here. So if we could have a clique, say for example, that could contain these two vertices here or this two here or in the more general case, if we can have a clique that contains more than one vertex from each of these groups here. So please check those that are correct and leave the other ones blank.

1 thought on “Construction – Intro to Theoretical Computer Science”

Leave a Reply

Your email address will not be published. Required fields are marked *