Transcript
the following content is provided under a Creative Commons license your support will help MIT open courseware continue to offer highquality educational resources for free to make a donation or view additional materials from hundreds of MIT courses visit MIT opencare at ocw.mit.edu okay let's start so today we're going to do some NP hardness reductions so let's just do a quick recap of uh p and NP so let's see so p is so have a decision problem so an input X and you have some algorithm a and it spits out an answer which is either zero or one so that's a decision problem and uh if a problem is in P this algorithm a runs in polinomial time so what about NP so NP is when the solution is verifiable in polinomial time so let's say you have an input X and some Oracle which is which can run in exponential time or has infinite computation time gives you an answer so you you get X and you get an answer which is either zero or one and you also get a certificate so it's called you have a certificate and given these three values you can you can verify whether the solution was correct or not in polinomial time make sense okay so clearly if you can compute the answer in polinomial time you can also verify in polinomial time so p is a subset of NP and so that's it okay so now NP hard problems are problems that are at least as hard to solve as any problem in NP and so now we're today we're go some reductions so I think you did some in class uh Nintendo games or something is that what we did okay so today we're going to do some less interesting examples but uh let's see so so how do we do reductions so if we know that we have an we have a problem a which is a hard problem and we want to show that problem B is hard so we want to draw this implication so if you want to draw this implication so this is equivalent to saying that if um if B is easy then a is easy sorry other way which is Contra positive so if you can so assuming that B has a polinomial Time solution a has a polinomial Time solution and that statement is equivalent to saying if a is hard B is hard so if you know that a is a hard NP hard problem we can say that b is NP hard problem so first we show so so if you want to show that b is an NP hard problem first we show that b is an NP and then we show that b is hard okay so the way we do that so the way we do this step is let's so your so a looks like this you have your lgorithm uh and it spits out an answer in 0 to one and B looks like this let's say you have an input Y and it spits out and answer is 0 to 1 and you want to find the function R which takes your X and sends it to Y so basically if you know how to solve B very fast then you can take an input to a you can so you take X you transform it and then you apply B and the condition is that a applied to X is the same as B applied to rfx so basically what you're doing is you're showing that a is Easy by showing that you can use so let's say B is easy we can use B to compute a so then a must be easy but since we know that a is hard that there's something wrong in our logic so B must be hard does that make sense yes s of okay anyway so let's move on to let's move on to an actual problem so the first problem we're going to reduce is the hamiltonian path so one so a wellknown uh NP so well known NP heart problem is the hamiltonian cycle so here our a is so it's a hamiltonian cycle what's hamiltonian cycle so hamiltonan cycle so let's say you have a graph so have this graph uh let me draw this out that's it okay so hamiltonian cycle is a cycle in the graph which starts at some vertex visits all the other vertices and comes back to the starting vertex so in this case we could do something like um go here and then take this vertex um go take this vertex take this vertex X and come back here so that is a valid hamiltonian cycle so this graph is hamiltonian cycle so the decision problem is here that given a graph does it have a hamiltonian cycle uh that problem is NP hard so you can't you can't solve it polinomial time so now the the new problem that we'll show is NP hard which is B is hamiltonian path so nowon path this is a very similar problem instead of cycle you just you require remove the requirement that you have to come back to the starting point you can just start anywhere and visit all the vertices and stop so for example if you remove this Edge this graph no longer has hamiltonian cycle but it has a hamiltonian path which is just this line so okay so so this is a simple reduction because the problems are uh very similar so the first step is of course saying showing that hamiltonian path is an NP so so that should be pretty clear because so what is our certificate here so if someone says okay I've solved the hamiltonian path and this is my hamiltonian path so the hamiltonian and he gives you a certificate which is the actual path so you can always look at the certificate check the path and see if it's a valid path and then you can verify the answer in polinomial time so that's the linear time verification so so this is this is true so now what we to show is B is hard so the way we do that is we do a reduction so the reduction is given an input to the original problem a so let's say an input to a is in the form of a graph so and now you have to transform this graph somehow to G Dash and then you have to argue that so this is this is the transformation R and you have to argue that the solution the answer that this will spit out is the same as the answer that this this would spit out so let's look at the transformation first anyone have any idea so let's say so you have a graph and it and you're that's and you're using that to solve the hamiltonian cycle problem so how do you transform it in a way that lets you cast into hamiltonian path formulation yes an edge not exact so you don't know so which Edge would you remove you don't know the H you can't find the hamiltonian cycle okay important point so there's no point doing this reduction unless this reduction is itself polinomial because otherwise this like hold strategy of transforming and then using B to find a doesn't work because if if the reduction is exponential time that doesn't help you so so so if so if you remove some edges you'll see that there is still a hamiltonian cycle but if you remove some Edge so still it doesn't so you can't tell like that so you don't know which Edge to remove so a better way to do about is this so let's say this is the rest of your graph and you just look at one vertex so look at one vertex V and let's say this is a directed graph if it's an undirected graph you can just like add one Edge there and one Edge back for everything so now you add a directed Edge along this sorry you look at all the directed edges so let's say you have some edges coming in and you have some edges going out so this is just a vertex and you just look at the rest of the graph and look at all the edges coming in and all the edges going out so this is an a this is the original problem and you transform this into you split the vertex into two so V Dash and vble dash let's say and in one of them you keep all the incoming edges and the other one one contains all the outgoing edges does that transformation make sense intuitively so what do you have here so here you had so let's say let's say this graph had a hamiltonian cycle so this graph had some cycle which like went up here did some did something and came back so it would go like this it would do the cycle and come back so it there was some cycle and since the cycle it contains V so now what you're doing is you're splitting apart V and disconnecting them so you'll still have if you look at the original path it's still there but it's it's been slit up into a path now it's no longer a cycle make sense so now let's let's argue this more rigorously so what we want to say here is that let's say there was a cycle here if there was a cycle here then is it clear that there is a path here because just take the same just take the same edges that you had before if you take the same edges they will now form a path instead of a cycle so cycle implies path does that make sense so the other way is a little more tricky so let's say you let's say you have a path let's say Okay Okay so let's say you had a path so that meant that that means that so let's draw this redraw this so it's more clear so we have this new graph where we have two vertices v-h and vble dash this has a bunch of incoming edges and this a bunch of outgoing edges so now let's say you have a hamiltonian path in this graph so what does that mean so where where can the hamiltonian path start can it start anywhere where going to start right because V Prime doesn't have any incoming edges so it can't be in the middle of the path so the it has to start here so it starts it does something in there and where can it end it can only end similarly in V Dash because V Das doesn't have any outgoing edges so it can't be in the middle of the path so it has to end in v Dash so now if you have a path like that and you go back to this for this this graph so V and V Das V Das and V double Das are now the same vertex and that just that path just becomes a cycle now so path implies cycle so that so now now what we have is previously what we had right so now now we know that a of X or rather a of G here is equal to B of G Dash so G Das was transformation also notice that the transformation was just splitting up out a Vertex so it'll like take depending on your representation of your graph it'll take something like constant time or linear time or something polinomial essentially so you get a polinomial deduction you after reduction you show that uh the answer to the reduced problem is the same as the answer to the original problem and and that means that this is this is also an NP heart problem by the argument given here okay questions does that makes sense yes so are you creating two veres for every vertex in the no just just one just pick any vertex doesn't matter because you have a cycle so if you take a take any vertex and split it apart you get a path sense else okay let's move on to the next one so gra a okay so the next problem is so let's chuse the so given a graph is there a k click does do people know what what a click is okay so what a so click is this so click is a set of vertices so let's say uh C subset of V so the set of vertices such that c is a complete graph so what is okay let's just draw a diagram that's really easier so okay so in this example so you have this graph draw the okay this one so look at look at this set of vertices every pair of them is connected to each other that means is that if you just look at just look at the graph with these vertices it's a complete graph so that's what's called a click okay and in this case this is a four click so you have four vertices this is a four click so so the so the decision problem is given a graph does there exist a k click so this is again known to be an NP hard problem so now we will use this to show that this problem is NP hard so this problem is independent set so again so given a graph what is an independent set anyone want to explain okay so what an independent set is this so let's say you have a graph which looks like so kind of complimentary to the definition of a click an independent set is a set of vertices such that no pair of them has an edge between them so in this case if you took this vertex let's say you took this vertex you took this vertex this vertex and this vertex so you can see none of these vertices have an edge between them so that is an independent set so in this case you're taking a set of vertices which have which is a complete graph so all of them have edges between them and in this case you're taking vertices which are completely disconnected so now we're going to try to find a reduction from this problem to this problem so first of all independent set is in NP is that clear how would you show that so how would you create a certificate which would tell you that so how would someone create a certificate which would convince you in polinomial time that this is an NP this that this is correct so just so the certificate would be just give you the independent set and you can check if something is independent set so let's say so given I let's Call The Independent set I so given a set of vertices you can verify that it's an independent set in polinomial time so you just like look at all pairs and check if there's an edge just some n Square n Cube whatever it's polinomial that's important okay so now let's look at a transformation so so again as before you have a which is which is given by a graph and you want to transform it to something so the important thing to note here is that in in Click you have so if you have a click C all pairs of vertices connected in a in I no pair of vertices are connected so what what should be a logical transformation that would map a click to an independent set what do you think you should do to the graph so it click becomes an yeah precisely yep exactly great so what ex so what all you have to do is if you want to turn a click into uh into independent set you just REM you just invert the you just uh what is it complement the adjacency Matrix so every Edge that does not exist now exists and every Edge that did exist is gone so you create a graph G Dash with the same same vertices except the edges are now complemented so the E bar just means the edges that were not so let let's just draw an example so let's say you had okay and okay and what does this become so let's draw the vertices first okay let's go one by one so let's take this vertex so let's take this vertex and what edges does it have so it goes here it goes here it doesn't go here so we draw edge here it doesn't go there we draw another Edge there and it doesn't go there so we draw another Edge there now this vertex it's connected to all of these except this one so that means that there's an edge there uh let's take this vertex it's connected to everything oh it's connected to everything okay let's take this one it's connected to these two nothing else so we need to connect it to this guy and I think that's it yeah uh similarly so proceeding this is connected to everything except that so I guess this goes there and I think that's it right or is there more uh three no okay so that is the complimentary graph I think so you can probably verify that so now let's look at the click in this graph so this is the click this is the largest click rather but this is a click you can have other clicks like for example this these three things are also a click so now look at what this is mapping to so this is mapping to this vertex this vertex this vertex and this vertex and you can see like that's an independent set so does that transformation make sense okay so now the proof should be intuitively cure so let's just go through it like mightly rigorously so let's say you have a click here so you a click here for every pair of vertices in the click there an edge between them and so if that maps to uh so let's say click c maps to uh it just maps to I so for all UV uh element of C you have UV element of e so for so since it's a click for every pair of vertices that that edge is in the original graph which means that UV is not an element of e for All U comma V element of I so for every element for every UV elementy we have this which means that does that make sense so that means that this is so the independ that's the independent set Criterion so now you have so you reduce click to Independent set and that means that independent set is now NP hard okay how are you doing on time okay let's so now let's do a more complicated example any questions on these two make sense okay so let's try this so let's start by raising something okay so this's the next problem so as before our a is G click and well so it says there's a click rather let's let's write this in this way click size greater than equal to K so that's the decision problem is there a click of size greater than equal to K and B is uh it's called Max two side so what that means is that so it is is somewhat like normal two set except so basically you have some clauses and you have some literals so each of these literals can take values one or zero and each of these Clauses is something like x i or XJ and actually there can be knots in front of this so let's call let's say x i not XJ or it can be other things so it's XI not XJ or not XJ XJ XI not XJ or x i XJ and so on and so forth so the just normal two so now the decision problem is to uh does there exist an assignment such that uh greater than equal to K Clauses so that is problem so is there an assignment to literals such that at least K of these claws are satisfied and so now we're going to show that it is with KCK click so again uh is it an NP so what is a certificate so how would you how would someone convince you that this problem like there's a Sol solution to this problem great give you a solution yeah so like give you an assignment of values to literals and then you can go through all the Clauses and check them so if they give you like X1 equal to 1 X2 = X equal 0 X3 equal to 1 and so on and so forth you can then go through and check all the Clauses and see if greater than k equal them are satisfied so this is an NP so now let's try the reduction so this is how the reduction goes so let's see so actually you have K click or greater than equal to K click rather so that means you have a graph uh with a set of vertices and a set of edges and let's say so let's say you have a click V Dash uh subset of v and mod of V Dash is greater than equal to K so now you want to somehow construct literals construct Clauses which will reflect this Behavior so first first of all this may not be clear right now but let's say we take some literals like this so let's say we take x i for all for all I element of V so for every vertex in the graph we take a literal so we have if the number of vertices is n we have n literals corresponding to each vertex also we take a dummy literal let's call it uh Z so now how do we write our Clauses so the basic the general idea here is that if if a Vertex is in the click we will assign it one if it's not in the click we will assign it zero so if we want so basically we want so everything outside outside of everything outside of the click is zero so this Clause not XI or not XJ so what is this what what is the value of this Clause normally so let's say XI and XJ are both uh are both Outside The Click so I and J are both outside the click that means that this is both of them are zero and so this is true what if one of them is inside the click and the other one is outside it's still true because one of these knots is one and therefore it's still true let's say both I and J are inside the click so you have so in that case you have X not of XI is0 and N of X is also zero so this is that's the only case this is false so the way we take care of that so we want we're trying to Max maximize the number of true Clauses in some sense this is like a hand baby explanation of why we using this Clause so what we do instead of taking all of the X ixj pairs is we just take X ixj such that um that I comma J is not an element of e so what does that mean so now if you had the graph which look like this now and let's label one two 3 4 so you would take not X1 and not X4 you would take not X1 and not X3 but you would not take not X2 and not X3 so what does that do that means that if you follow the assignment according to the click rules for there for every I so if I and G are both in the click this this Clause will not be included does that make sense what set of Clauses we're taking okay so let's continue and it'll be probably hopefully be a little more clear so the other sort of clause we're going to take is x i r z and the other one is Xi or not Z so the reason we're taking these is that if you wanted to Max Max two set on this on this alone you could just set everything to zero and that would give you a maximum so to sort of like not do that so to sort of minimize the number of things that you said to zero you doing this so this is this is just hand way we argument why you're doing this so let's actually try to do some analysis on this so let's say we do this transformation so do the Clauses make sense does the first Clause make sense if you have so you have not x i not XJ for every i j which is not in the graph so how does this work so let's say you have uh let's call it V Dash such that size of v- is greater than equal to K actually let's just let's just make size of v- equal to K so if you have a click of size greater than equal to K of course you have a click of size equal to K you can just throw away some of the vertices so you take you take a v Dash such that this size is equal to K and you set x i is equal to 1 so you set x i equal to um one if I is element of V Dash zero if I is not an element of B Dash make sense so you set everything in your click to be one and everything outside to be zero and let let Z equal to one so you're starting with the assumption that so you're showing One Direction so you're showing that given that there is a click of size greater than equal to K and now we are going to construct a Max two set instance which has the satisfied number of classes greater than equal to K and then we'll show the other direction so so now let's look at how many Clauses we have to be satisfied so so the first first type of clause was not of XI uh or not of XJ so how many of these Clauses are being satisfied so first case I and J are both outside V Dash is the Clause satisfied in that case yes because you're by definition if they're outside V Das they're both zero so the knots are both one so they're one so if the I andj are outside V Das you're good so what about the case when one of them is inside V Dash is the cloud satisfied so that yeah because one of them is one of one of them is zero which makes the knot one and the whole thing is it's an R so it's it's let's say both of them are inside V Dash let's say both I and J are inside V Dash then this class just doesn't exist because of the condition that IG had not elements of because if it's inside the click then that Ed obviously exists and therefore this Clause is not not in the set of Clauses we're using so essentially every Clause of this form will be satisfied and how many Clauses of this form are there the number of Clauses of this form is just e bar where e is the complimentary Edge set of that graph that's e bar okay does that make sense so yeah all right uh next Clause is x i or Z so since we have we took Z to be one uh this Clause is always satisfied so this just gives us mod of V because so every so this is for every I so I should have mentioned that uh for all I and this also for all I so for every I so the how number of uh XI are V and that's it so the third type of clause is x i or uh not of Z so not of Z since Z is one not of Z is zero so the only cases where this Clause is true is where is when XI is one and XI is one only inside V Dash so the number of CLA is satisfied here is mod of V Das and mod of V Das is what it's just K can you see this the visible okay uh does that so all three cles make sense so can you see why the first one is uh it's the size of e bar because all the claws are satisfied the second one also all the Clause are satisfied because Z is one so that's every every Clause is just the number of vertices and the last one it's only satisfied for the cases where XI is one and XI is one only inside the click so that gives you the K things in the click so now we can finish formulating our transformation so our transformation was you set um so uh what was the transation yes so these are these are our Clauses and now we have to set the the K right so the max 2 set was with a condition of K so here you'll set it to be mod of e bar plus mod of V plus K so does make sense so basically so our our Max two side problem so the reduction to the max two side problem so we specified the Clauses we specified the literals literals were x i for all IV and the dummy Z we specified the Clauses and we specified the threshold we're trying to achieve so that so those three things completely specify the max two side problem okay so okay proceeding so observe that this just this so we just showed One Direction we showed that if there's a click of size greater than equal to K we reduce this to a click of size exactly k then we did then we did this assignment and we showed that the total number of Clauses being satisfied is mod of e bar plus mod of V plus K and that is that is the first Direction so now we shown that so uh if you have a solution to uh click we have a solution to Cas Max casad so now we do the other direction so let's say we have a solution to Max casad that's okay let's do this let's do it here okay so let's say uh okay so this part is a little more tricky so we start with Max Kad has a number of satisfied Clauses which is greater than equal to mod of e bar plus V plus K so we know that so Ma so we know that maxat accepts so we need to know that so we Define we Define a v Dash uh then this V Dash is in the graph for uh click as the set of vertices I such that X of I is equal to 1 so if our Max say has that many things then there is some assignment to XI which satisfies that and we take that assignment and for every value that is one we put that in a it's not it's not a click yet but it's it's it's a con it's a click under construction so we like make this click under construction and we assign it values of all the vertices which are currently labeled y one but you don't know if that's a click right it could not be a click it could be something like let's say this is the current V Dash so V Dash could be something like you have all these vertices and they s let's say some of them are connected but then you have this dangling guy so this is not connected this is not connected so it's not a click so let's say let's say um this is vertex I and this is vertex J and this whole thing is V Dash and let's say somehow you have this anomaly you have that this guy is not connected to all the vertices so let's take one such pair and let's just say we remove we remove XI so we just take we just take the XI and remove it from V Dash and what that equates to in the max case at is setting XI to zero so we take the original satisfying assignment and change the value of XI so let's see what that does so we take and set x i equal to zero and X I was originally one so uh let's actually write it down so x i uh or rather I comma J is not an element of e but so these IG were in the supposed to be click but the I comma J is not in the edge set so it's not actually a click so the way we resolve that is just like we do we say okay let's let's just forget about this vertex let's say just not in the click so we set XI to zero and what does that do let's look at how that affects the number of set Clauses so the first one is XR Z so now here we have not set the set Z to be one this this has been like this is something in thing but we can just we can if Z is equal to zero we can just replace Z by not of Z so like the Clauses are symmetrical with respect to Z right so it's x i or Z or x i not Z so it doesn't matter which one we set to be one or zero like one of them is one one of them is zero so let's just say that Z is one without loss of generality so what that does is so initially this Clause was one because Z is one and now it goes to one and nothing changes okay it's good sounds good what about the next one so now we have x i or uhor not of Z so however so not of Z is zero and XI just went from being one to being zero so what that what happens here is that initially the Clause value was one and now it goes to zero so we so that's not good because we just like we could have now now we no longer satisfying Max case at possibly because we had some number of satisfying Clauses which was above our threshold but now subra now we lose a clause and we could be going below the threshold but then we look at the third clause and what that does is so let's let let's say look at this specific Clause the one which said that x i and XJ uh note that this Clause exists because uh X ixj is not an edge in E and therefore by that condition this Clause is exists in the set of Clauses so what was the value of this Clause initially before in the initial assignment what was the value of this Clause not that x i and J are both in V Dash so what was the value of that this clause in the original assignment before we set XI to zero what was the value of XI in the original assignment so yes why is it one yeah so XI was in V Dash that's why so it's One X XJ was also in V Dash because that that's the anomaly we saw right there was not an edge in the click so this was originally so this was one and this was one so this was zero and this was zero and or z r Zer is so this used to be zero so what happens now though does it change so it changes to one right because XI goes to zero now this thing becomes one and so change to one so there may be other Clauses with XI But realize that not of XI is so if XI is changing to zero not of XI is changing to one so whatever happens here it'll only increase the number of Clauses that are being satisfied so you lose only one but you can but you gain at least one So eventually it does not change so does not change the number of satisfied Clauses so that's important so what we did is we started with some satisfying assignment that we assumed existed and then we just changed a variable and we said that it's still at least as many Clauses being satisfied so we did that and now we have one less vertex that is that is violating uh let's P this down so we have now we have one less vertex that is violating the click property so now we can now we can take this step it's like setting XI to zero we can just repeat this so how long do we repeat this so we repeat this still there are no longer any violations so every time we find a violation so once we delete x i so this is gone so now we look for the next violation the next violation is this Edge so there's no Edge there so we can either take this Vertex or let's call this SK so we can either remove XK or remove XJ so we remove one of them and if you see once you remove that you'll be end up it'll end up with a three click so what happens is once we repeat this if until v-h is uh quick so you could doeses that make sense why you can do that so you just keep deleting vertices until this is a click and that those those Clauses that Clause condition is still satisfied you still have greater than equal to that many Clauses so now let's look at what we have we have V Dash which is a click and x i is equal to so when is X I so once you have done this like process as many times as you need when is x i equal to 1 so remember that so V Das is also being updated every time you set XI to zero XI is being removed from V Dash so that property is always satisfied that Define v- equal to I for x i equal to 1 that property is always invariant that means that even after doing all these repetitions you still have x i equal 1 if and only if um if only if i z and v Dash and zero otherwise so does that make sense why that property still holds so you have a click and you have this assignment so that should take you back to this so remember where we took a click of size K and we found that if you go through all the algebra you will find something which is like um you will go through and you will get mod of e e bar plus mod of V plus mod of K right so here you have click so forget about what you did before so just like consider like this is an assignment according to those rules and those rules give give you that you should get number of satisfied Clauses is equal to mod of e bar plus mod of V plus mod of V Dash realize that V Das here is not K does that make sense because V Dash is just you started with some set you you started deleting some elements you throw them through them away randomly but you ended up with some V Dash and by this argument you had e plus Mo of V plus mod of V Dash e bar from this Clause V Das from V from this Clause V Dash from this Clause so you going end up with this and you know that because of because of what we showed here does not change the number of satisfied Clauses it's still greater than equal to uh mod of e bar plus mod of V + K and you cancel this you cancel this and you get you get mod of V Dash is greater than equal to K which means that that which means that you have a click of size greater than equal to K questions does that make sense really all of it okay that's good any case so so let's go back and see what what we are doing here so the way you're doing NP reductions is NP hard reductions is you take a problem that you already know is hard you take any random in any arbitrary instance instance of that problem and you transform the input and into an input to the problem that you're trying to show is hard so you take problem a which you know is hard you transform the input into an input for problem B and then you show that if you can solve a Sol problem B you'll be able to solve problem a but since you know you can't solve problem a in polinomial time you know that you can't solve problem B in polinomial time and the and the other important thing to notice here is that the reduction needs to be polinomial time so let's look at this reduction for instance what are you doing here you're taking uh you're taking every vertex you're making a clause and how many Clauses do you have well you have about n Square Clauses here you have all n Clauses here and you have order n Clauses here the time to construct that is like roughly or n squ so you're constructing the causes in polinomial time so you have a pol polinomial time reduction and if you reduce a known NP hard problem in polinomial time to an unknown problem you can show that as NP hard okay uh I don't think we have time to do another problem so