15. NP-Completeness

welcome everyone um back to um theory of computation so we are now at lecture number 15 and if this is an important lecture um well all of our lectures are important but this is i'm going to introduce one of the major topics that we're going to see going on in various forms through the rest of the semester which is the notion of a complete problem in this case it's going to be an np complete problem and i think some of you have probably heard of that concept already maybe you've seen it in some courses or other but we're going to do that in a in a rather careful and formal way over the next couple of lectures so we are following up on our previous discussions about complexity time complexity we defined the time and non-deterministic time complexity classes as you may remember the classes p and np talked about the p versus np problem looked at some interesting algorithm for showing problems in p called dynamic programming and we started to move toward our discussion of np completeness with the introduction of polynomial time reducibility which is related to some of the earlier reducibility notions that we discussed in the computability section so let's [Music] quick review um what it means for one problem to be polynomial time reducible to another this follows our pattern of reducibility concepts where um if a problem is reducible to another problem and that other problem is solvable then the first problem is solvable so if a problem is reducible to an easy problem that problem becomes easy too um and the kind of reduction that we're going to be looking at here are the mapping reductions but now where the reductions are computable in polynomial time and so we had this um result we mentioned last time that if a is polynomial time reducible to b and b is in p then a is also in p um [Music] so that's going to be um critically important for the you know for the for the whole um of discussion that's coming um our intuition about pnnp um repeating that here um the np problems are the ones where you can verify membership easily as opposed to being able to test membership easily those are the problems that are in p the verification typically requires some kind of a certificate that establishes kind of a proof that the input is a member of that language um and the big question of the field which remains an unsolved problem is whether p equals np it's called the p versus np question and we don't know the answer so whether there are problems that are in np um solvable and nondeterministic polynomial time typically these are problems that involve searching whether they can be solved in polynomial time typically without the searching um and uh if p were equal to np then you could always eliminate searching and a p were different from np then there were cases where you need to search um and we don't know the answer to that uh so in the direction of exploring uh this this question and its ramifications we introduced this problem called sat these are the boolean formulas which have an assignment that enable that event makes them evaluate to true um so we call those satisfiable formulas and uh we um mentioned but have not yet proven and we will not prove until the next lecture on tuesday that there is this theorem uh kind of a very remarkable theorem that says that if you have uh you take the satisfiability problem and if it is solvable quickly then all of the np problems are solvable quickly so if sat is in p then p equals np so in a sense sat is kind of you know the uh it's sort of the super np problem in the sense that all of the difficulty of any np problem is is embedded within sat so if sat becomes easy then all of the other np problems become easy um and we'll eventually prove that but right now we're kind of setting up the um terminology to allow us to do that um so uh anyway we'll we'll we'll get there um so the the the key ingredient for proving this kook 11 theorem is polynomial time reducibility what we're going to show is that every problem in np can be polynomial time reduced to set so every np problem can be converted into a set problem and so working toward that because when you think about it you know there are infinitely many problems in np and um being able to show that all of them are reducible to sat as in a sense kind of um you have to prove a kind of a higher level theorem it's not just a single reduction we're kind of exhibiting a schema of reductions which shows that all of these problems can be reduced to set um and kind of developing our um you know our intuition toward that direction we're going to look at some specific polynomial time reductions today um and we'll start out with a reduction between two problems we have not yet seen one of them called threesat and the other one called clique so on this slide we're going to introduce those two problems so remembering again about boolean formulas we're going to consider a special class of boolean formulas a restricted form of boolean form formulas called conjunctive normal form and so this formula here in particular is in that conjunctive normal form um so just remember um i was explaining some of this to someone else uh earlier this morning showing some of these slides and it was pointed out that not all of you may have be familiar with these um the boolean operations of and and or uh so this is the or symbol here this is the and symbol here you know they operate you know hopefully you've seen the just the concept of boolean and or or is in a sense a little bit like a union um and it's like an intersection and the the symbols here are kind of a little bit similar to the union and intersections you know the intersection the union intersection symbols themselves like or the v-shaped is a little bit like a pointy union symbol and the in the um upside-down v-shape is a little like a pointy intersection symbol so maybe that's if you haven't seen those seen that connection before maybe it's interesting to observe that but anyway um what makes this uh formula be in conjunctive normal form well the conjunctive normal form formulas are organized in a certain way they have um these groups called clauses within the parentheses that are added together that are connected by these and and operations um and within those groups which are called clauses the um elements are ored together those elements are going to be either variables or variables with negation negated variables um so uh just to repeat that uh these well i'll just just state those those variables or negated variables are going to be called literals um and the ors of a bunch of literals are going to be called clauses okay this is just the standard terminology in the field okay so um a literal is a variable or a negated variable and a clause is an or of literals okay just a definition all right so we have a bunch of these clauses here each of the clauses has an or of of liter of literals in it now a chomsky conjunctive normal form uh formula i guess they're both c and f's but uh it's conjunctive normal form formula is one that's written as an and of these clauses okay so we take these clauses which themselves are ors we and them together we get a formula that's conjunctive normal form conjunctive stands for and i think uh conjunction is an and um and then a three cnf is a cnf where each clause has exactly three literals so for example this particular formula is a cnf but it's not a three cnf because it has at least two clauses which violate the condition of three literals per clause this one is okay obviously this first clause and the three sat problem so this is the first of the two problems we're going to be talking about the three sad problem is the satisfiability problem restricted to these three cnf formulas so this is the collection of setup of three cnf formulas which are satisfiable so you can think of it as a kind of a special case of the sat problem where we only care about formulas of the special kind um this being a special case you might imagine that this might be an easier problem to solve but in general it turns out not to be as we will see this is just as solving this special case is just as har as hard as solving the general case for satisfiability um now let's turn to the second of these two languages up in the headline uh the clique problem um so for that we gonna turn to graph theory so we're going to consider graphs you know points and lines connecting them and we will say that a clique in a graph is a collection of nodes collection of the points that are all pairwise connected by lines and a k click is one where you have case arch nodes so here we have a three click four click and five click um and the clique problem is to try to find cliques of a certain specified size embedded within a given graph so you'd like to know whether you're going to be given a graph and it targets click-sized k and you want to know is there a subset of the nodes in the graph of size k that are all connected to one another that's the cleat problem um so obviously um the clique problem just as with the satisfiability problem is a decidable problem you can just try every possible subset of k nodes and see whether it constitutes a clique but that's in general going to be an exponential algorithm if you have you know you know k is a large value like it might be half the size of the graph you might be looking for a very large clique then you have to try many many subsets in order to see whether uh any one of them is a clique it's also going to be and i hope you get this intuition this is a problem that's in np the cleat problem is an np problem because you can easily verify that a graph uh has a k click just by exhibiting the click okay um now uh uh so the clique language here is you're given a graph and a k and you want to know does the graph contain a cake league um and what we're going to show is that these two problems are connected that the three set problem and the cleat problem are related in that you can reduce in polynomial time three sat to click okay so this is um you know at you know just standing back at it back for a minute you know that seems kind of surprising there's no real reason you know uh obviously anyway no obvious reason why there should be a connection between three sat and click click they look very different from one another but we do give that uh we will give that reduction and um it then that implies that if you can find a way of solving the clique problem quickly that'll give you a way of solving the the three set problem quickly um and that's going to be the whole point of this um so we're going to show this over the next slide or two um this this polynomial time reduction and this is something i'm going to walk through it slowly but this is one where you it's really important to try to get a sense of how it's working um uh because this is the kind of thing that we're going to be doing a lot of and you're going to be asked to do it also on the homework and and possibly on the final exam i hate to use that as the motivating force here but at least it might be one motivation for some of you that you have to understand how to do uh this kind of a reduction okay so you know i i think at a high level what's going on is we're showing how to recode a boolean formula satisfiability problem into the problem of testing whether a graph has a clique um so let's see if we have any questions here that are coming up in the in the chat um okay so i this is an interesting question here can we always convert a boolean formula into conjunctive into conjunctive normal form first of all yes the answer is you can always convert a boolean formula into an equivalent one in ins into in cnf but in general that might make the formula exponentially larger [Music] so just the mere fact that you can convert formulas into into conjunctive normal form doesn't mean that solving um that you know that solving uh um conjunctive normal form uh formulas for testing satisfiability of the of the cnf formulas is going to be as hard as testing the general case because just the conversion might be exponential um there's something more uh more a little bit more complicated going on um than that so let's uh um let me just see here uh if he is a satisfiable formula which is not in cnf can be so a similar um you know similar question so the questions that i'm getting are about converting formulas uh to cnf um so yeah you can do it but not in polynomial time in general because the resulting formula you get might be much larger um if you if you're looking for an equivalent formula if you're not looking for an equivalent formula then you know of course then depending upon what you're looking for you might be able to find something smaller um ah this is a this is a i guess a good basic question why is clique in np um because isn't doesn't verifying that you have a clique require going through all the possible cliques once i you have to understand what verifying means verifying means you can verify something if you're given a certificate in the case of a clique the click problem the certificate is the clique um so once you have the certificate you can do the verification in polynomial time finding the certificate of course might be difficult so you only think of np in the context of having that certificate so in a case for like compositeness the certificate might be the factor um you know anyway i hope that's you know it's there there are problems sometimes with what the certificate is is not necessarily obvious um but there can be a certificate um for um showing that the that the input is in the language but in the ones that we've done so far maybe you can argue that this certificate is sort of an obvious thing but it's not always an obvious thing um okay why don't we move on then um so let's see how do we do this polynomial time reduction from three sat to click okay here we go um so i'm just going to give a reduction that's that's that's what the definition means i'm going to give a way of converting formulas to pairs a g and a k where the formula is going to be solid satisfiable if and only if the graph has a k click okay so let's kind of a little bit do it by example and in order to do that so here's going to be a formula now it's in three cnf that's what i need you know in order to be doing this reduction i'm converting three cnf formulas into clique problems we have to a little bit understand what it means when we say uh we talk about the satisfiability of a formula like this because it's going to be helpful in doing the reduction you know obviously it's satisfiable means that the form you can find an assignment of the variables so you're going to set each of these variables a b and c and so on to true or false and you want to make the whole formula evaluate to true but what does that actually mean [Music] it means that because of the structure of the formula that making this formula true corresponds to making each clause true because the clauses are all added together so the only way for the formula to be true is to make each clause true and to make a clause true you have to make at least one of the literals true so it's another way of thinking about uh satisfying this formula you need satisfying these and a satisfying assignment makes at least one true literal in every clause it's really important to think about it that way because that's what's going to be um [Music] kind of the basis for doing this reduction and all of the reductions it's kind of what makes three set easy to think about in terms of its satisfiability if you had a sort of a general um satisfiability problem and you had a satisfiable formula there's no sort of obvious way of sort of seeing what the satisfying assignment looks like but here we understand what it looks like it has that very special form making one true literal in every clause at least one true literal in every clause okay so now we're going to do the reduction so i'm going to take from this formula you and you have to understand you know i know for some of you you know you're going to be you know chafing why am i going so slowly but i want to make sure that we're all together in understanding what the rules of the game are and what we're trying to do um we're trying to convert this formula into a graph and a number so right now my job is to do this reduction is to exhibit that graph okay so i'm going to do that in kind of two steps i'll first i'm going to tell you what the nodes of the graph are then then i'll tell you what the edges of that graph finally i'll tell you what the number k is that's the way this polynomial time reduction is going to work and we have to also observe at the very end that the reduction that i'm given giving you this procedure for building this graph can be done in polynomial time but that i think you'll see once i'm done that that's pretty obvious okay so first as i promised the nodes um so the nodes of this graph are going to correspond to the literals of the formula every literal is going to become a node in the graph and it's going to be labeled with the um name of that literal so it's every node is going to be labeled an a or b or or c bar and so on so here it goes okay so those are the nodes of the graph g one for each literal in the formula okay labeled as promised now i have to tell you what the edges look like the edges are going to be um i'm going to tell you what the edges are by first telling you what they are not i'm going to first explain to you what the forbidden edges are what what edges i'm going to promise not to include and then the ones that i will include are going to be all the others okay so what are going to be the forbidden edges first of all um the the forbidden edges are going to be of two types one is the edges between nodes that come from literals in the same clause so i would just call that no edges within a clause okay so for example these three nodes will not be connected to one another and i'm going to indicate that by writing red dashed lines which means there's not an edge there okay those are those are forbidden from having an edge okay so these three have no edge and the same thing for every other uh triple of three nodes that come from uh clauses okay those are no edges there and there's one other category of edge that i'm forbidding and that are edges that can that um go between inconsistent labels and the nodes with inconsistent labels so for example between a and a bar those are inconsistent you know nothing's wrong with a going a to d those are not inconsistent those are just different labels or going from a to a that's okay but from a to a bar that's that's not allowed um so that's going to be another forbidden edge or for example a to a bar here for b a bar to a or for example from this c bar to c forbidden okay so imagine you're going to write down all of those forbidden edges and then once you've done that uh those are all of the the forbidden edges and then after [Music] taking those away you're going to be putting in all the other edges possible so for example as a let me just uh gray those out so they don't interfere with the picture b from a to a to d um there's going to be an edge um because those are not forbid you know a to a not forbidden because they they're in different um they are in different uh clauses and they're not inconsistent they're they're consistent with one another so here are a whole bunch of other i'm not showing them all becomes very messy but uh here are all the other edges between nodes uh which are where there isn't there's no pro within they're not forbidden okay and that's that's the graph that's g g is all those nodes and those edges um which are not forbidden now i just have to tell you what k a is k is going to be the number of clauses that's going to be the size of the clique i'm looking for in this graph g that i just spelled out for you and i'm going to claim that this graph here that i just described will have a k clique k is the number of clauses exactly when fee was satisfiable it's kind of kind of cool you know um if he is satisfiable then there will be a cake leak here and if he was not satisfiable okay clean so we have to we're gonna prove that as a claim on the next slide okay so k is the number of clauses all right um any questions on that on that construction so i've done with the construction what's left is to argue why the construction works so far so good let's move on okay um so um so here is that very same construction i eliminated the red uh forbidden edges these are the ones that were remaining plus you know anything else that was not forbidden that was the same formula that i had from the previous slide now i'm going to claim that that formula is satisfiable exactly when g has a k click now why in the world is that so this is an if and only if it's proved in both directions and this is going to be the typical kind of thing that you're going to want to do when you're exhibiting a uh you know one of these reductions which is you're going to have an opportunity to do that um and we'll do do that too in our examples uh okay so now uh what i'm what i want to show is that uh if fee is satisfiable so let's prove the forward direction if p is satisfiable then g has a k click okay so first of all if fee is satisfiable that means it has a satisfying assignment okay now here's a common confusion i'm not sure whether it's helpful to sprinkle the confusions in along with the discussion but in case you're worried you might ask well how do i find that satisfying assignment i thought that was you know exponential exponentially hard to do this is a proof this is not an algorithm okay we're just trying to argue the con correctness of this construction so there's no longer any concern about how to find an assignment i'm just saying if there isn't a sign if there is a satisfying assignment then something will happen something that then then um something will happen in particular then we will show that g has a cake league so let's say fee is satisfiable so it has some assignment let's take that satisfying assignment and remember that in any satisfying assignment uh to a formula in cnf that makes at least one literal true in every clause so let's just pick one of those there might be several clauses which have multiple true literals in that case just pick one of them arbitrarily okay so i don't know what the i don't have this sort of indicated on this diagram here but imagine you know maybe in the very first clause a was true in the second clause b was true in the third clause e compliment ebar was true and you know not not you know e bar was true which means e itself was false but e bar was true and that's the way each of those clauses in turn uh got to be true you know in this particular satisfying assignment because you're going to pick one true literal in every clause and now from that choice of literals one per clause i'm going to look at the corresponding nodes in g and i'm going to claim that those nodes taken together form a k click okay so first of all do they have the right number of nodes well sure because i'm picking one node per click i already said k is the number of cliques so i'm getting exactly ka nodes so i have at least the right number of nodes but how do i know they're all connected to one another those nodes uh that i just picked well they're all connected to each other because i'm going to say well because there were no forbidden edges among them and remember that we put in all possible edges except for the forbidden ones so how do i know there are no forbidden edges well what were the rules for being forbidden means they two nodes in the same clique in the same clause well i'm picking one node per clause so i can never be having two nodes from the same clause so i'm never going to run into trouble with uh the first condition of being forbidden so what's the second possibility for being forbidden is that i'm picking two nodes which are inconsistent well how do i know that i didn't end up with two nodes with inconsistent labels that would be bad because then they would have a forbidden edge and what my result would not be a clique how do i know i didn't end up picking um uh in this group i pick a and in this group i pick a a bar well because they all came from the same assignment those are all of the true letters they were all true literals in clauses it's not possible that a was true in this clause and a bar is true in that clause because if a is true here a bar has got to be false it can't be the true literal in this clause so i cannot have any inconsistent any inconsistent nodes appearing among the nodes of my clique and so they're not in the same clause they're not inconsistent so the edge has to be there and that's going to be true for every pair of nodes in that clique in that in that group of nodes and that's why it's a click um so that proves one direction now we stop to prove the other direction because we have to say well if g has a k clique how do we know that ph is satisfied so that's the reverse so let's just take any k clique that's in g and how do i know i can get from that a satisfying assignment to the formula um uh good um getting some good questions here in the chat but let me just move on um take any uh so proving the reverse this the reverse direction but we're assuming we have a cake leak to take any such k-click now first of all you observe that it's got to have one node in every clause it can't have two nodes in the same clause or zero nodes in in a clause first of all it can't have two nodes in the same clause why well because those nodes are never connected to one another so that they cannot be both in the same clique because all the nodes in a clique are connected to one another um by construction by the way we construct a g nodes from the same clause are not connected so they cannot appear in a clique together so um there's going to be at most one node from every clause appearing in this clique but and but but appearing in in this clip but we also have we know we have k notes so that means if there is at most one per um per clause and we only have k clauses that means every clause has got to have one you know if some clause is missing or note then there's going to be some other clause that has two so we know that every um that this clique that would that g has has exactly one node in every clause so how do we get from that a satisfying assignment so what we're going to do is take the current corresponding literals that correspond to that one node in the that was in the uh clique take those literals and set those literals to be true which means setting the variable to be true um or setting um you know if the literal was a bar then setting a to be false because you want a bar to be true you want to set the literals to be true well now we're setting um there's one note in each clause we're setting one literal uh the corresponding literal true so that's going to set one true literal in every clause so that means it's going to be satisfying there's one thing that one has to really to be careful here to double check to make sure that we're doing this consistently that we're not being asked to set you know a true and also a bar true because then that would not be possible but a and a bar are not connected so it's we're never going to be trying to set both a and a bar true if so we're going to be trying to set a true we're never going to try to set a bar true because those are not those a and a bar cannot be in the same clique they're not connected to each other okay so that is the argument um and lastly i claim we're not going to look at this in detail that it's kind of obvious that this reduction can be done in polynomial time namely if i give you that formula you can write out that graph in pretty easily there's no hard work to be done in writing out that that graph or counting up the number of clauses so that's that's the proof that i can reduce three statically um and it tells you also that if i could solve click quickly then i can stop threesat quickly and this is the whole point because i can convert now clique problems to three sat problems no no i couldn't i'm sorry i got backwards convert three set problems the clique problem so if i can solve quick click easily then i can solve three set easily right i just showed a way of converting these formulas to graphs so if that's so that says if i can solve the graphs easily then i can solve the formulas okay why don't we uh turn to some oh question checking but you know we can also um why don't i i'll launch a check-in but we'll we let's just see i'm seeing many many questions here which are actually what my check-in is about i'll turn it back to you guys uh okay so where did we use the fact um that we have three uh literals per clause what does this thing just work even if we had any number of literals per clause um what do you think we're having a we've got a tight race here hmm uh truth is losing out unfortunately all right oh it's really close but still okay uh one more okay it's neck and neck okay almost done 10 seconds are we done here okay that's it uh ending polling uh yes truth is thank god um yeah it works for any size clause we didn't use the fact that it's a three c and f it could have been any number here uh so it's well we've got a i guess it's a plural plurality here though that not a majority um no we didn't where did we use three in any of these argument i didn't mention it maybe you were imagining that that is going to be part of it but three does not come into this at this discussion at all if you think about how it's why it's working um even if we had you know one of these clauses had 10 literals in it as long as k is the number of clauses and we don't connect any variables any literals internal to a clause this whole argument is going to still work so please check that make sure you understand what's going on because i can see that a good chunk of you have not got this right um uh so i got a good question here uh what if it's only just one big clause so it's like the whole formula is just one big war so what does happen in that case good question so in that case um uh so the you know suppose has one big clause with a hundred literals that's the whole formula it's just a big war so we know the formula is going to be satisfiable by the way obviously um so if you look at the corresponding g it's going to have 100 nodes because there's one for every literal um none of them are going to be connected to each other because they're all in the same clause um so it looks like we're going to be in tough shape trying to find a clique there because there's no edges at all everything's forbidden but what is k k is going to be 1 in that case because there's only one clause and uh kind of a degenerate case but a clique with just one you know just a single node is it counts as a one clique because it's just one node there's no need for any edges at all it still counts as a clique so it'll still it'll still work out um uh let's see what else here uh that was kind of a fun question that you asked me thank you um uh there are a lot of questions um i think we're actually pretty near the break also we'll just see yeah um so why don't i um oh many many questions here uh so i i think i'm gonna start start the clock going down for our um our coffee break and um and i will take some of these questions i'll try to answer some of these questions oops um try to answer some of these questions um afterward uh all right good all right um so i got a question about making sure why nodes don't have inconsistent labels if i understand the question correctly um so these would be nodes um so i never put edges between nodes with inconsistent labels that's the rule that's my construction i get to i get to say how the construction works so those two nodes with inconsistent labels can never be in the same clique because there's no edge between them so i'm not sure that answered the question there but that was uh um let's see so getting another question here since any boolean formula can be converted to cnf does that mean um is sat polynomial time reducible to clique as well monomial time reducible to clique but not for the reason that any boolean formula can be converted to c and f because that conversion um is going to be an exponential conversion in general the conversion to c and f so you have to be careful about what we mean by converting a formula to cnf um uh so also getting questions what happens in the case of one set well we didn't really talk about one set uh suppose or i guess so the question is suppose there's only a single literal per clause that's an interesting another sort of edge case here what happens under those circumstances so um there's only a single literal per clause um uh so you have to work out what happens but in that case um uh all the clauses just have one literal in them and now they have um uh um the only way uh this if you think about what is a when you have a one cnf so there's only um one literal per clause the only way that can be satisfiable is you have to make each literal true because there's no warring anymore so every literal has to be true in the assignment so that means you can never have inconsistent literals um and that's the only case when you would not have an edge because you're not the forbidden is the forbidden condition won't happen because you don't have more than one uh node per per clause every clause is going to have just a single node in it uh so it really comes down to whether or not you have an inconsistently labeled um inconsistent clauses i i didn't explain that super well but it's the the argument still works there you should check it for yourself um so this is a basic question how do we see that f is polynomial time i i'm not sure i want to expend a lot of you know a lot of discussion on that because the the conversion from the formula to the graph is kind of a one-to-one you know every no every uh literal becomes a node um the rule for when edges are present it's a very simple rule so i guess i would argue i'm not sure what what more to say it seems pretty clear that the conversion that reduction is polynomial time computable i mean if you wrote a program to do that it would operate very quickly um is it possible for g to have a k plus n clique where n is greater than zero and does that matter now if you think about it the biggest possible clique that this graph g could have is k it could never have more than uh uh you know a bigger clique because two nodes in the same uh clause are never connected you only have k clauses so the answer is no you cannot have a bigger a bigger than a k click it's just not going to happen does each clause need to have the same number of literals i don't see why um uh so question is why are we worrying about threesat um since it didn't seem to matter here there are other examples where it does matter i i i'm actually not sure if we'll see one or not but um there there are cases where it does matter um let me just see if there's any quick questions here uh somebody's saying doesn't does do we have to worry about there being a polynomial number of literals so you have to think about what you what that question means the size of the input which includes all of the literals is n so there's going to be at most n literals um because that's the size of the input uh the i mean at most uh and literals appearing so you don't have to worry about that being polynomial because by the way we're we're defining the size of the input is going to be at most n literals i hope that's clear uh okay when we talk about power okay so this is a good question when we talk about polynomial time it's polynomial in the representation of of the input which is if you want to think about it in terms of bits that's fine or whatever it's not going to matter if you use some larger alphabet but the number of symbols you need you know in your fixed size alphabet the number of symbols you need to write down that input in whatever your reasonable encoding is is going to be n and it's going to be polynomial in n polynomial in that length of the input um so another question is does sat reduce the three set yes we that we will see um sat actually does polynomial time reduce the three set not by converting to an equivalent formula but by some more uh somewhat more involved argument uh than that okay why don't we move on some of these are going to come out anyway in the lecture okay so now let's talk about mp completeness because we've kind of set things up we're not going to prove that you know the basic theorem the cook 11 theorem about mp completeness but at least we'll be able to make the definition okay here's our definition you know what it means for a problem to be in be complete um uh so a language b is called np complete if it has two properties number one is that has to be a member of np and number two every language in np has the polynomial time reduced to that to that language to that np complete language in order for it to be np complete okay so simple picture has to be in nnp and everything in np reduces to it um and so that's kind of the magical property that we claimed that that sat has sat for for one thing is obviously in np and as we the cook 11 theorem shows or will show everything in npe is reducible to sat so that's going to be our first example of an np complete problem um uh so now uh and we're going to get what we claimed also for sat that if sat or any other np-complete problem turns out to be solvable in polynomial time then every np problem is solvable in polynomial time and and that's immediate because everything is reducible in polynomial time to the np complete problem so if you can do it easily you can do everything easily just by going through the reduction okay so the quick level theorem as i mentioned is that sad is np-complete and we're going to actually prove it next lecture but let's assume for the remainder of this lecture that we know it to be true because so i'll use the terminology of problems being np complete uh assuming that we know um that we have uh sat as empty complete okay so we're gonna we're gonna be using some of the things that were proving next lecture uh just in the terminology that we're going to be talking today okay so here's the picture here's the class np and everything in np is polynomial time reducible to set sat itself is a member of np but i didn't want to show it that way because it makes the picture kind of hard to uh hard to uh hard to display so just from the perspective of the reduction everything in np is polynomial time reducible to sad we'll show that next lecture another thing that we'll show next lecture is that sat in turn is polynomial time reducible to three sat so three stat as you remember are just those problems that are in conjunction three are in three c and f um and then what we showed today is that three set is polynomial time reducible to clique so now taking the assumption that sat is np complete so everything is polynomial time reducible to sat which is in turn polynomial time reducible to three sat in in turn reducible to click these reductions as we've seen before composed um you can just reply apply one reduction function after the next if each one each one individually is polynomial the whole thing as a combination is going to be polynomial so now we know that three sat is going to be also np complete because we can reduce anything in np to stat and then to three set and then we get a reduction directly to three sat by composing those two reductions and then furthermore at the clique so now we uh have several np complete problems and moving beyond that we have the hand path problem which we are going to talk about next and we'll show another reduction um in addition to the one we just showed to click now one going from three set to hand um okay uh so in general i think the the the the take away message is that to show some language as np complete you want to show that three sat is polynomial time reducible to it um uh okay some good questions coming in i'll try to answer those so you're going to retake 3sat and reduced to c that's the sort of the most typical case or you might have there's going to be other examples too we might start with another problem that you've already shown to be np complete and read and reduce it to your language so it doesn't have to start with reset though often it does um okay why do we why is this concept important so i would say there are two reasons um and this is going to get a little bit at the uh some of the chat questions um first of all if you're faced with some copy new computational problem you've got some robotics problem um that you want to solve in your thesis and you need to some algorithm about whether the robot arm can do such and move in a certain such a way and involve searching you know possibly searching through a space of different kinds of motions and you want to know you know i need a either i'd like to have a i like to find a polynomial algorithm to solve that problem i'm using this as an example because this actually did happen to one of the former students from this class who was working in robotics and they actually end up proving that the problem that they were trying to solve is np complete um so um uh that's useful information because even though knowing a problem is np complete doesn't guarantee that it's not in p because conceivably p equals np what it does tell you that if you show if you have a problem that's np complete and it does turn out to be in p then all then p equals np so the tremend would be tremendous surprising consequences of of your problem if it was known to be np-complete ending up in p so generally people take a proof of np completeness as powerful evidence that the problem is not in p even though it's not quite a proof it's powerful evidence that it's not in p and so you might as well give up working on trying to find a polynomial algorithm for it because if you do you know you don't have to worry about robotics anymore you're going to you know become famous as a complexity theory person um so i wouldn't worry about so if you show problems np complete you can pretty much assume it's almost certainly not in p um now there's another reason related to the to the for the theorists uh to be care about mp completeness and that is if you're trying to prove p is different from np or p equals np as one of the chat questions is raising um you know the problem you know in order to prove p different from np you know the most likely approach is you pick some p problem in np and show it's not in p right that's what it would mean for them to be different you're going to pick some np problem and show it's not not a p problem well um one thing would be terrible is possibly p is different from np and you pick the wrong problem like suppose i'd spent all my time trying to show you know back 20 years ago i'm working really hard trying to show composites is not in pain which is would have been perfectly reasonable to do because composites is an np and was not known to be in p 20 years ago um and then i invested tons of effort to try to prove because you know i like number theory or god knows what to prove that composites is not in p and then it turns out composites wasn't in p it was the wrong problem to pick even though p might be different from np but what np completeness guarantees is that if you work on a problem which is np-complete you could you can't pick the wrong problem because if any problem is in np and not in p an np complete problem is going to be an example of that right because if the np complete problem is in p everything in np is in p so if np is different from p you know the complete problems are not in p so you might as well work on one of those so those are two ways in which np completeness and has turned out to be is an important concept okay so here's a check-in um uh again this you guys are kind of getting maybe you're getting started to think the way i think you get is some at least one of you would ask this question in the chat um which language that we've probably seen is most analogous to sat okay atm etm or zero to the k1 to the k uh obviously this is maybe subjective you may have your own interpretation of what that means this in a sense perhaps no right answer but what do you think uh okay that's it um i don't know i don't know how in the world that you could see this problem is analogous to to zero to the k1 to the k but okay um i'm sure you have your reason um yes this is a lot like eight atm why well because for one thing we showed in a homework problem that all um touring recognizable languages are reducible to atm mapping reducible to atm so that's a little bit like the notion of completeness that we have for satisfiability um because all np problems are going to be reducible to sad um and the other thing too is that once we start once we uh we started we want to show other problems are undecidable we reduced atm to them and that's also very similar we're going to be reducing sat or threesat so it's indirectly from sat to other problems in order to show that they're np complete so that they're hard they're they're that they're hard in a sense and so uh in kind of both those ways atm and sat are kind of playing similar roles one key difference however between atm and sat is in the for atm we can prove that it's undecidable but for sat we don't know how to prove it's outside of p that would those would be the analogous situations um and uh so the the story for sat which is kind of easily solved by a diagonalization argument for atm there's reasons to believe that we will see later that diagonalization is not going to work to prove sat outside of p and besides that we don't really have any good methods um so uh anyway uh let's move on why is etm less analogous uh i know because atm was the first problem we showed undecidable and sad is kind of the first problem that we're going to be showing np complete i guess that would be my answer um okay let's continue so let's show now that handpath is np-complete assuming that we know sat or threesat is np complete okay so we're going to give a reduction from 3sat to handpath that that that that's what that's what this is about it's just like what we did for clique but now for him path um and and this is going to be very typical in in these reductions typically what happens is that you're trying to simulate a formula use you know a boolean formula for satisfiability from the satisfiability perspective you're trying to simulate that formula with some sort of structures inside the target language which would be hand path and so what the lingo that people use is that you're going to build gadgets to simulate the structures in the formula namely the variables the literals and the and the clauses okay these are going to be substructures of the um either you know the graph in this case that you're that you're building um we'll see what that means so let's take a formula here and uh let's again try to imagine how we would reduce that to the hand path problem so the reduction would produce a graph no it would produce a hand path instance so a g s and t want to know is there a hamiltonian path from s to t in the graph and this is going to be not the whole graph but this is going to be a substructure in that graph the next slide is going to have the global structure of the graph graph but here this is going to be a key element and it's we're going to call that the variable gadget okay what does it look like i don't know if you can see it on your um clearly enough but these uh edges so there are four outside notes here the edges connecting them are all kind of pointed downward and then there are these horizontal nodes here and there are edges connecting them both left to right and right to left okay there's a row of these horizontal nodes okay so you get the picture of what this looks like um you have to look carefully to see the arrowheads i maybe should have made those a little bigger okay so now um uh whoops let me let me just see so now if we're trying to get from this node to that node imagine now you're trying to build a hamiltonian path because this is going to be a part of that graph g that i'm constructing now remember for them there to be a hamiltonian graph that means you have to go through every node in the graph so if i want to get from s to t the only way i'm going to be able to to go to hit these horizontal nodes here is um by picking them up uh as i go from s to t so the only possibility is if you think about it is it would be for the sequence to go like this if you could if that comes through for you so the the path would go from s to this node and then through these hops of along these horizontal nodes and then down to the bottom node here okay so that's one way that you can get from here down to there and pick up all the other nodes along the way which is they're not going to have any other possibility possible ways of getting to them so i'm going to call that a zigzag okay but there's another way to get from s to the bottom node okay which is going to be by doing sort of the dual going to the right then going out to the left and then down to the bottom i'm going to call that a zigzig okay and uh with a little kind of little diagram here just to summarize what it means and this is the this is the classic thing for a variable gadget because it's a structure that when you're trying to think about how the object that you're asking whether it exists or not the hamiltonian path how it relates to that object it's going to have two possibilities which are going to correspond to the variable variable being set true or false in the formula so we're showing how to