Date: 2018-08-30
Timezone: -05:00:00
14:01:42:Presenter: Okay. Let's see if it works. No.
14:01:52:Presenter: Okay. It seems to work now. Okay. So let's begin and we check the time, I don't want to.
14:02:20:Presenter: Now just in time excellent, then, okay. So one announcement is that there is discussion section today at four.
14:02:33:Presenter: Which would be kind of a part of Office Towers participation is not required to commended etc. So let's see today's Thursday.
14:02:51:Presenter: I might have to lower the volume, I think it seems to some feedback loop the one on this.
14:03:05:Presenter: No, okay. I hope the loop would not be too bad. If might be the better. In fact.
14:03:12:Presenter: From the style will seek, okay, so.
14:03:27:Presenter: So the fact today starts the day a think it's the third pierced and we're going to put into speaking about him.
14:03:40:Presenter: Completeness. Okay. What do they talk about last lecture? So I talked about the optimization problem.
14:03:58:Presenter: Decision problem that NP those are optimization problems where you given a question. So and into problem looks like something like the following. Let me take a new problem.
14:04:01:Presenter: Before independent set.
14:04:08:Presenter: This is the name of problem. And then we have an input.
14:04:19:Presenter: Sometimes I would refer to an input of Apollo is an instance, it's the same thing. And so the input is the graph in a parameter. K.
14:04:26:Presenter: Then there is a yes to question. Right is.
14:04:34:Presenter: An independent set.
14:04:44:Presenter: So in G of size larger equal in case.
14:04:53:Presenter: Of times K don't really matter that much, right. So we have a problem like that and two.
14:04:57:Presenter: Mind you worked as an independent set in the graph you have a graph.
14:05:00:Presenter: Doing nice house.
14:05:18:Presenter: How's an independent set is a set of healthy cells that make this one in this one.
14:05:30:Presenter: In such that no pair of them are connected with an edge to listen independent set in our masking is that if independent of size.
14:05:35:Presenter: So this is the decision version.
14:05:48:Presenter: Okay. And usually, there are two other version of the problem the next one is the optimization version.
14:05:54:Presenter: Whoops optimization.
14:06:02:Presenter: The materialization version ask for you know, give me the largest independent set in the graph. This is the maximum.
14:06:13:Presenter: Mention problem usually, it's either maximization immunization problem in the smallest of the largest an and usually it's very easy to know which one.
14:06:20:Presenter: Interested in be cause it is the empty solution of everything is a valid solution. And then you have to go into an interaction.
14:06:32:Presenter: And so this is the optimization version and the next one is the same batch version the search version says.
14:06:41:Presenter: If you can.
14:06:49:Presenter: Given the graph give me the largest give me an independent of size at least Cal give me the largest independent set.
14:06:58:Presenter: Right. So already versions of similar, right? One ask is there yes. No, that would ask for the number.
14:07:07:Presenter: So if it don't want to ask for the real subset and when we speak about the NP completeness. We speak only about the decision version.
14:07:14:Presenter: But it's only for technical reasons. Essentially cause the three versions are equivalent. And I will talk about that.
14:07:25:Presenter: Short. Okay. So we have the NP problems which have the property that given instance, if the answer is yes.
14:07:33:Presenter: There's the given as an independent that of size. K, we can easily check it, right? All we have to do.
14:07:41:Presenter: Is if somebody played down to review. S the community the list of the K vertices in the independent set.
14:07:49:Presenter: And I can just should go in check that, indeed the case vertices delisted are an independent set, right.
14:07:57:Presenter: So given instance, if the answer is yes. There is a short proof in this proof can be verified in polynomial time.
14:08:05:Presenter: If the answer is no, you know we have no guarantee an and of course the issue here is that.
14:08:11:Presenter: And for this problem the natural algorithm is just to play or subset of vertices which takes exponential time.
14:08:23:Presenter: Right. So this problem is in fact independent set. But is not only in NP its effect NP complete what was the NP complete problems.
14:08:35:Presenter: NP complete problems where soup we had one problem that we knew was NP complete, which is three SAT.
14:08:44:Presenter: NP complete problems or problems such that if you can solve any of those problems in polynomial time, then.
14:08:51:Presenter: All the problems in NP can be solved in polynomial time. So.
14:08:56:Presenter: So let me in fact, the vision directed formally of note.
14:09:10:Presenter: Let me like it for peace up okay. If solve three SAT in quality time.
14:09:12:Presenter: Okay.
14:09:21:Presenter: Or problems.
14:09:24:Presenter: Pink.
14:09:27:Presenter: Can be solved.
14:09:32:Presenter: In polynomial time.
14:09:43:Presenter: Okay. And also the collection of politics in a little NP complete our priorities not clear that any part of it.
14:09:56:Presenter: Complete. But cook proved that three SAT is NP complete. Right. And form their own people proved a huge number of other problems.
14:10:06:Presenter: Complete literally by now the hundred if not powers and in of problems virus optimization problems that are NP complete.
14:10:14:Presenter: In particular, you for most problem, you can search the web there is a website dedicated to listing.
14:10:22:Presenter: Problems in the start to since on in the tool to prove attempting is NP complete is a polynomial time.
14:10:30:Presenter: Reduction which I didn't really define in the last lecture. So let me talk about it. Now.
14:10:34:Presenter: Okay.
14:10:45:Presenter: So polynomial term reduction will write it as a X smaller equaled and *** why.
14:10:54:Presenter: Right. This is especially a way to say the following if we can solve.
14:11:04:Presenter: One polynomial time.
14:11:07:Presenter: Then.
14:11:10:Presenter: We can solve.
14:11:15:Presenter: X implement them.
14:11:30:Presenter: Okay. You can interpreted operations reduction of polynomial time to one this statement says as far as polynomial time.
14:11:38:Presenter: As far as exponentially time verse polynomial time is X is the are easier than why if we were told why polynomial time?
14:11:47:Presenter: X appointment time. So this is something about the harness in the way such reject the reduction moves is.
14:11:53:Presenter: I assume that you're giving me a black box for why server.
14:12:03:Presenter: For one is I built out of it is sort of forex summary presented algorithm that works in polynomial time?
14:12:04:Presenter: And.
14:12:10:Presenter: So I assume that this store for why is polynomial time server.
14:12:13:Presenter: For why?
14:12:23:Presenter: Important talking, you know if you want to think about it in a in problem in terms a stink about I give you a library.
14:12:33:Presenter: That is a function of can, you know positive that can solve why it works in polynomial time and polynomial reduction.
14:12:48:Presenter: Put another reduction is just an algorithm that take an input, for instance of X in polynomial time using this plaque box for why.
14:12:55:Presenter: It solved it in polynomial time. So that's polynomial in action and the way the reason why it works.
14:13:01:Presenter: Because if we could solve why put over time, then this algorithm would solve X in polynomial time, right?
14:13:08:Presenter: In reduction to are here and burned to use reductions as a tool for proving hardness. But.
14:13:17:Presenter: The way to think about it is that, you know all programming is essentially reduction, right. Unless you're going in programming in assembly.
14:13:29:Presenter: Now that you're going to software libraries. You can think about software library that, you know you're reducing whatever think pastor Frank to do your reducing it to available tools at hand. So.
14:13:36:Presenter: Reductions are really critical to the way to think about things now as I mentioned in the last lecture.
14:13:44:Presenter: We can about polynomial pipe support number time is something that looks like that, which is really a way to say that there exist.
14:13:52:Presenter: You know I'm not going to going to form a lecture definition but there is a constant such that.
14:14:00:Presenter: The number of relation performed a constant C for the number of operation performed by the algorithm for input of.
14:14:07:Presenter: You put any smaller than this. Right. And all attention is just a way to say we don't care about the exact value of the constant.
14:14:17:Presenter: Okay. Now the important thing about this notation in white all these polynomial time reduction makes sense is be cause.
14:14:31:Presenter: Polynomial time is closed under substitution and what do by that if I give you an.
14:14:38:Presenter: And end script time algorithm, but, you know this algorithm that take every step it makes culture some black box.
14:14:44:Presenter: I don't know what it is. But this blocks the running time of this plaque marks is let's say.
14:14:53:Presenter: Into the fault each is maybe enter the 7 okay. So this is the square coils.
14:14:56:Presenter: Two black box.
14:15:04:Presenter: And you have to be careful here. So let's assume that the black box is just all the output it returns.
14:15:09:Presenter: He did pull force wired I care about that will be clear shortly. And this is the running time.
14:15:12:Presenter: Of black box.
14:15:23:Presenter: So if I have been algorithm like that the running time of the algorithm is going to be, and to the severed.
14:15:29:Presenter: The powers two right, which is open to the full 10 in this case this is still form polynomial.
14:15:39:Presenter: So if you substitute a polynomial into a polynomial you still get a polynomial. So below polynomial time is closed under this kind of chaining.
14:15:47:Presenter: And that's really why we care B cause or out or induction are going to be polynomial time assuming we have a black box.
14:15:52:Presenter: A problem. And if this block boxes polynomial then we get the running time that is polynomial.
14:15:56:Presenter: Okay, an.
14:16:06:Presenter: Question of the time, no cause.
14:16:11:Presenter: Yes, that's a very good point. Thank you.
14:16:14:Presenter: You know this is not equal.
14:18:36:Presenter: Okay, that answer the question how many professors you need to change a battery one but very slowly, okay.
14:18:45:Presenter: So let's go back to, okay. So in fact, I wanted to this was a very good point steak?
14:18:56:Presenter: So let's think about to remind you accept all I have a black box, right disagreed with N squid time.
14:19:03:Presenter: But it was using this black box that running into the fervent, but instead the output was eating 3 2.
14:19:11:Presenter: It was one bit output. But let's say that this is not true. Let's affect assume that they have an algorithm.
14:19:19:Presenter: The trans linear time, but it output interested input.
14:19:23:Presenter: Hey, now put some output.
14:19:31:Presenter: You know that output is not a bit can be should be some whatever output and the claim is that now.
14:19:37:Presenter: What is the running time in this case, I bore every black box attached linear time is.
14:19:42:Presenter: I call it more central time. What will be the running time of this algorithm?
14:19:54:Presenter: Excellent. No. So here is a simple algorithm. I'm going to take the black box and all it's going to do it back to take it input.
14:20:02:Presenter: Okay. And it's going to copy it twice. So it could be sex it went to output X X.
14:20:11:Presenter: X, you just going to take the input and output two copies of it is clear linear time, right?
14:20:17:Presenter: And now my algorithm is just going to want it take the output of this procedure fit it to itself.
14:20:19:Presenter: Quicktime.
14:20:28:Presenter: So in the beginning of the input is going to be sized in all right in the second iteration it's going to be two end, right. Because I.
14:20:39:Presenter: Input in the eye deterioration. It's going to be true to the items. Right. And if I write in school time.
14:20:48:Presenter: To be all to the two of square times N which is exponentially. So when you change polynomial time.
14:20:54:Presenter: Algorithms, you're allowed to do it on a constant number of times if you do it more than constant number of times.
14:20:57:Presenter: Strange things happen.
14:21:10:Presenter: Okay. So that was type comment, but it kind of political to the moon discussion. Okay. So in the last lecture what did he do the last lecture we talked about three sites?
14:21:18:Presenter: We talked about two start, which is polynomial increase at and I talked about clique.
14:21:29:Presenter: And I, you know the speed of light sketch during the polynomial time reduction from three SAT to click.
14:21:37:Presenter: If you look in your homework one of the question is essentially proving the reduction in the other direction.
14:21:44:Presenter: Okay. So this problem that essentially equivalent polynomial equivalent.
14:21:57:Presenter: Okay. So N big problem and equivalent means that if I can solve one controlled. The other implement and vice versa.
14:22:01:Presenter: An let's cook so.
14:22:15:Presenter: So let me maybe talk a little bit about decisions version verses search versus optimization. So in the clique version.
14:22:24:Presenter: I'll give you a graph I give you K asked to Easter clicker size K.. Right at the bottom is ation version would be.
14:22:31:Presenter: Give me the largest clique in research version would be to give me the side of the largest clip.
14:22:37:Presenter: And the search version will be give me the largest clique in the graph give me the vertices of the clique.
14:22:47:Presenter: Now the claim is that all those three versions. And this is kind of universally pooh one has to be careful, but.
14:22:50:Presenter: So clique.
14:23:07:Presenter: To be the nation. So for clique the decision version. Let me prove to you that it's equivalent to the optimization version.
14:23:13:Presenter: Back to the power is ation version output in numbers. K the size of the clique in the graph.
14:23:20:Presenter: Right. So I claim that they can't if I have control of decision version I can solve the optimization version how would they do it.
14:23:34:Presenter: Yeah, I could even be small canoes binary search, right? So there are, I'd optimization function can just look around the value of K start increasing. K.
14:23:43:Presenter: Until reaching the first case for which a decision version says not there is no clique, and then you just return the previous value is the largest clique in the graph.
14:23:50:Presenter: So this is and, of course, if it construct optimization I can solve the decision. So there are a quiver.
14:23:58:Presenter: Essentially the same polynomial equivalent of one controlled data from a type the more interesting version is the saturation.
14:24:03:Presenter: Okay, so clique.
14:24:11:Presenter: Click search. So I give you a graph. I ask you give me the largest clique in this car.
14:24:19:Presenter: So, of course, if we could talk this search I control the decision, right cause I need to decide in the clique is of a certain size.
14:24:25:Presenter: I'm going to compute the largest clique, which is compared to size to the threshold given, so that's easy.
14:24:36:Presenter: So the most interesting version is the other direction, right? Given the black box that can solve decisions. How do we solve the search version?
14:24:47:Presenter: Okay. So let's go through it, right. The input is the graph. Right. And first I already argued that if I did decision version is a black box.
14:24:51:Presenter: I can compute the size of the clique. So I can match as well assume that I have dropped.
14:25:00:Presenter: Nations version is a black box, right? So the term is ation version tells me what the largest clique in this graph.
14:25:08:Presenter: And you don't we assuming a black box here was the black box, you know we're magically assuming it running polynomial time.
14:25:15:Presenter: So now what can I do I want to find this clique in the graph. Right. And the size of the clique, I call.
14:25:22:Presenter: I can't optimization version want it tells me caters to size of the largest clique in the graph escape.
14:25:33:Presenter: Now, you can do I can just go to the text, and I look at this vertex, and I can decide whether or not. It's part of the clique, how would I do this.
14:25:43:Presenter: You're just promoted from the graph. I ask is the new graph is the clique size still K.. If he has.
14:25:50:Presenter: And then this vertex was not important, and we go on. So we literally go and we tried to assassinate every vertex in the graph.
14:25:57:Presenter: Keeping the environment that the maximum clique size does not decrease in the end of this process will leave.
14:26:07:Presenter: We are left with K vertices ones which are the vertices of the maximum of the largest clique. So this property.
14:26:19:Presenter: That you can reduce the ascension version to the decision version. This is called self reduction sometimes pecked sensually two for all.
14:26:31:Presenter: NP complete problems. So any particular observed that optimization version in the clear search version are not NP complete problems.
14:26:43:Presenter: They're not NP complete problems be cause there not a decision problem. So there are optimization version of the such version of NP complete problems.
14:26:46:Presenter: Are sometimes refer to as NP hard problems.
14:27:00:Presenter: Sometimes now if you have problems NP hard problems is the definition is just any problem that if you could solve in polynomial time.
14:27:08:Presenter: Then can solve all the problem is NP in polynomial time. Okay. So.
14:27:15:Presenter: For now, let's go back to the pumps. Let me check on the prime.
14:27:28:Presenter: Okay. So what is that what I'm going to do in the rest of the lecture in it doesn't lecture i'm going to go through a long list of problems.
14:27:35:Presenter: You know that are all NP complete. I'm not going to pull out of the men are NP complete.
14:27:41:Presenter: The proofs of most of the caller mentioned not all of them are in the class not.
14:27:49:Presenter: The slides and, you know, and you can, of course find proofs online of all of those toaster basic problems.
14:28:00:Presenter: In the main purpose of this shopping list of problems is to first kind of exposure to the problem is we care about in this class.
14:28:10:Presenter: If you want to solve and also I kind of want to convince you that almost all interesting problems.
14:28:20:Presenter: Already complete. Right. And literally every natural almost any natural optimization problem, you would come up with which is.
14:28:30:Presenter: This script and the problem is all we cannot solve it efficiently because it's NP complete and but you know, on the other hand.
14:28:47:Presenter: Some sense we could solve only problems that are polynomial time fission tree. So it sounds sense, remaining of the remainder of this class would be.
14:28:53:Presenter: What can we do right? You know the one that when we to think about it's really big darkness, right?
14:29:00:Presenter: Everything is hard, not if it's possible. But there are a few things that we can solve it polynomial time.
14:29:12:Presenter: And, you know, and the rest of the classroom be dedicated to learning about those problems, and the second thing is that a lot of the stuff we learn in this class.
14:29:20:Presenter: Comes to address this issue, right? So for a lot of problems. We cannot solve them, but we can give it approximate solution.
14:29:29:Presenter: All, you know we could use some techniques dynamic programming to some some problems that are in general might be hard.
14:29:39:Presenter: But, you know, for certain cases we can solve them efficiently internment of what I talk we can there are a few lights.
14:29:53:Presenter: In the darkness in this class is all about the lights but you know, if you're going to learn astronomy and you're going to lean learn planet you should die of about the space in between.
14:30:00:Presenter: M in order. So as I said a lot of those problems. Are you know kind of good problem.
14:30:08:Presenter: The feeling for what we care about. Okay. So I mentioned already two problems. So in fact, I mentioned, let's start from three SAT.
14:30:19:Presenter: Okay. So please start was formula that our precision f, right? But you can remove the restriction.
14:30:27:Presenter: On the size of the clothes you can allow any size you want to this side is just anything f.
14:30:37:Presenter: Then, of course it NP complete be cause one control reduction you can for employment mentioned you can try and think about the reduction.
14:30:52:Presenter: Somewhere directions of electively easy some reductions are how in some reductions are really good ridiculously out, but if you can see how did you know, I'm not sure I could come up with them if you give me a week.
14:31:08:Presenter: Result signal, right already. Okay. So Csat you can easily show that three started starter equivalent and the moment polynomial equivalent, right? Everything every time.
14:31:15:Presenter: Equivalent in polynomial equivalent and the more interesting problem is circuit satisfiability.
14:31:31:Presenter: Okay. So circuit SAT through ability I give you H a circuit, right? So circuit is the end of Gates and all this time.
14:31:39:Presenter: Your input into the circuit there is one output and I ask is there an input for the circuit such that it satisfiable.
14:31:48:Presenter: So one control one needs to think about how to do it, but you can model you can reduce you can given a circuit appeals.
14:31:57:Presenter: Generated sexually aside formula waitress at formulate equivalent. That is Fortified Belle if and only if the original circuit is satisfied.
14:32:08:Presenter: So end I should mention that a lot you have to be very careful. But for a lot of the NP complete problems.
14:32:15:Presenter: If you're making small changes there probably still NP complete, but you have to be very careful B cause.
14:32:21:Presenter: There are exceptional cases will you make a small change and suddenly we know how to solve it sufficient.
14:32:36:Presenter: Like two such versus three, sup, okay. Now I mentioned clique and I mentioned independent set.
14:32:47:Presenter: Right. So clique was find the largest subset of vertices is such that every pair of them connected and the question was.
14:32:58:Presenter: Clicker size. K independent that was the compliment right. Can you find K vertices that every pair of them are not connected?
14:33:02:Presenter: Just to parliament polynomial equivalent, how.
14:33:08:Presenter: So I give you a graph in asking you to the click of size. K.
14:33:17:Presenter: Course more click and there's another graph and ask you is there an independent set of size. K, what's the relationship between those two?
14:33:25:Presenter: Problems with the control one of them frequently here in just complimenting off that's all you have to do.
14:33:37:Presenter: So that's silly an as I in the last lecture. You know, I kind of sketched why.
14:33:46:Presenter: Clicker preceptor quibble and more or less, okay. Let's move to a mall interesting problem. This is ops.
14:33:54:Presenter: I guess I want to vent but this is one of the most deadly named problems.
14:33:58:Presenter: Okay.
14:34:07:Presenter: So it's called vertex cover what is vertex cover estimating heat. It's all about the edges of the graph.
14:34:17:Presenter: So you want to find. So the way to think about it is that you want to put to pick subset of vertices think about.
14:34:26:Presenter: Develop. This is the two peak is God's right. So you want to pick a minimum set of vertices.
14:34:33:Presenter: That cover all the ages, right? So every edge is adjusted to one of the first.
14:34:42:Presenter: So in this case, for example, this would be a valid vertex cover. So we see is the subset.
14:34:44:Presenter: Subset.
14:34:54:Presenter: And it's of the vertices of the graph such that for any edge U V in the edges of the graph.
14:35:07:Presenter: Let's see. So this is the formal right. Let me write it in the lazy thing using X.
14:35:14:Presenter: Visa mix of both, of course, right.
14:35:22:Presenter: So for every edge one of the input is in the subset what a trivial solution for vertex cover.
14:35:31:Presenter: Because we think so this is if everything is a solution that it we are interested in minimize ation version.
14:35:42:Presenter: So you're given a graph and the parameter 10 in your ask is the red vertex cover smaller than came this cough.
14:35:52:Presenter: So that's the position problem. Let's observe that this problem is in NP the decision problem. If I claim that the graph has.
14:35:59:Presenter: Vertex cover of things. K, I can just least give you a list of the K vertices is and you can verify that, indeed.
14:36:01:Presenter: Every edge is being covered.
14:36:13:Presenter: Okay. So that in vertex cover is NP complete that why misting it. Let me heat. Why?
14:36:25:Presenter: White NP complete what the reduction is. So let's assume that came about X covered red vertices here and I look at vertices.
14:36:30:Presenter: But are not in the vertex cover what property do their hair.
14:36:43:Presenter: Done in the permanent, right? So in fact in solving vertex cover problem is equivalent to solving the independent set, right. So.
14:36:53:Presenter: If there is an int if there is a vertex cover here of size. K if and only if.
14:36:56:Presenter: There is an independent in.
14:37:03:Presenter: Of size in minus K and vice versa and the proof is easy, right? So let's see why the proof is very.
14:37:09:Presenter: If this is was not cool in the green set is not independent then two of them has an edge.
14:37:16:Presenter: But this edge is not guarded. It's not covered. So the red set is not a lot X color.
14:37:25:Presenter: The end and I direction is also is like if I have an independent set then already edges in the graph.
14:37:32:Presenter: Must be adjustment to one of the edges that are not in the independent. So it is a vertex cover.
14:37:45:Presenter: Okay. So vertex cover is essentially equivalent to independent set. So this is in NP complete product. Okay. Let me talk about.
14:37:52:Presenter: Edge. This is more often be careful. So edge cover.
14:37:55:Presenter: Right? So what about edge cover.
14:38:02:Presenter: So edge covered as the name suggest it's all about the bill to service.
14:38:08:Presenter: Okay? So I would like to pick.
14:38:23:Presenter: It's subset of the edges, right such as every vertex is covered in this case, which I just, I would pick. Let me pick this one.
14:38:29:Presenter: This one, and this one, okay.
14:38:36:Presenter: So this is an edge cover. So this problem is clearly meant P.. Well, the decision's version, right. So.
14:38:46:Presenter: Is there an edge cover of the graph of sites modeled in case of the Polish cleaning NP an such tactic to say.
14:38:50:Presenter: NP complete but it's not this problem can be solved in polynomial time.
14:39:07:Presenter: And I would try to remember essentially it follows from matching algorithms that will see later in the lecture.
14:39:14:Presenter: It's kind of an easy application of matching once you know how to solve matching in polynomial time. So I hope that I will remember to show you how it's done.
14:39:21:Presenter: But this is kind of what's going on. Right. This is a mind field, right? You know things.
14:39:32:Presenter: Just change teams in summer leader polynomial and it's like, okay, why we don't really know, okay, dominating sense.
14:39:41:Presenter: So dominating set to give you a graph.
14:39:44:Presenter: An.
14:39:54:Presenter: I would like to pick a minimum number of vertices science say this one, and this one such that.
14:40:02:Presenter: Every vertex is either in the dominating set or adjust into a vertex in dominating step. Okay. So this problem.
14:40:11:Presenter: Also NP complete. Of course here. So again, if we take all the vertices it clearly dominating set. So this is going to be mean nation.
14:40:21:Presenter: Relation problem. And instance is the graph and can ask is there a subset of K vertices as such it all the vertices is.
14:40:26:Presenter: Dominated, okay, so this is dominating set.
14:40:30:Presenter: Oh.
14:40:43:Presenter: One. Let's take them to me and cycle because it's more harm.
14:40:51:Presenter: What do party in cycle talking cycle? I give you graph.
14:41:04:Presenter: Yeah, that's not a very interesting graph. Unfortunately. And let's try to make it more interesting.
14:41:09:Presenter: Yeah, that would make it interesting.
14:41:24:Presenter: Okay, an. Yeah, so far examined onion cycle. I give you a graph in Alaska keys to the simple cycle, I'm not allowed to repeat vertex.
14:41:39:Presenter: Such that I visit all the vertices of the graph. Exactly, once right. So if you think about it is crafted into does not have a Hamiltonian cycle.
14:41:48:Presenter: Right. And it kind of easy to see right be cause the cause of those two vertices right. So.
14:41:54:Presenter: You know, if you visit this vertex that you have to go through this vertex at this vertex.
14:42:01:Presenter: Right in after visiting this vertex you have to choose what to do, right? If you decide to go here.
14:42:09:Presenter: When you're dead, right? We cause then you cannot get out, so that's not the right thing to do, so you go here.
14:42:19:Presenter: But then this vertex become isolated, right? So does this graph doesn't have a Hamiltonian cycle and, you know, this is easy. But once it, woo.
14:42:27:Presenter: Large enough craft is problem becomes very hard. Of course this problem is in NP, right to give you the graph in effect claim.
14:42:34:Presenter: Yes. I just give you the permutation of the vertices and you could just go through this permutation and verify that indeed.
14:42:44:Presenter: You visit every vertex. Exactly, once in the third and you visited all the vertices. So this problem is in NP.
14:43:01:Presenter: So that's that is, so this is NP complete problem. And this is already. So the standard proof is the reduction from Priests Art.
14:43:12:Presenter: To hamiltonian cycle, and the reduction you consider reduction in the class notes on the slide. It's super hairy.
14:43:22:Presenter: One of the things were you give me give me a preset formulated build this Bizarro graph in your view that it is a limit and cycle if and only if the region.
14:43:30:Presenter: Formula be satisfied. So I'm not going to go into the details of net and there is a top version.
14:43:38:Presenter: In the path version. I'm I give you the start and end vertex and ask if there are particles.
14:43:48:Presenter: Develop. This is exactly, one's is there is the directed version with the graph is directed watering showed he was done directed version.
14:43:54:Presenter: Doesn't make there are all those versions of NP complete.
14:44:04:Presenter: Okay. I want to speak about, of course before going any further about the Funk Funk Funk version of the problem.
14:44:06:Presenter: Which is only layer?
14:44:20:Presenter: Well, let him cycle. So we learn cycle is a give you a graph.
14:44:29:Presenter: And ask you is there a way to is a cycle.
14:44:35:Presenter: That visits every edge. Exactly want in visit all the edges in the graph.
14:44:39:Presenter: Okay. Anybody knows what the status of this problem.
14:44:48:Presenter: So you're not allowed to visit the vertex multiple time in the cycle. So let's see you go here.
14:44:52:Presenter: It's time to do it.
14:45:03:Presenter: Right. This is a cycle in this case, so give you the cough and asked me still lonely and cycle.
14:45:07:Presenter: Or computed. So anybody knows what's the status of this problem.
14:45:11:Presenter: Yes, it can be solved in linear time.
14:45:14:Presenter: So N plus m.
14:45:23:Presenter: Well depending whether you want to decision version of the search version in here is the number of edges in the graph and.
14:45:29:Presenter: So I'm not going to prove this. This is kind of a standard descript marketing might have seen it.
14:45:37:Presenter: It's central e all you need to do is you just start walking B picking arbitrary vertically start walking in the graph.
14:45:44:Presenter: Until you visit to vertex you already do already visited if you do that. And you found a cycle.
14:45:52:Presenter: Remove the cycle repeat in the end of this process your recollection of cycles given to cycle. It's very easy to do.
14:45:59:Presenter: The surgery the local surgery that make them into a bigger cycle to take all the cycle and use.
14:46:05:Presenter: Do you use surgery them together cutting redrew them? So that you get a one big cycle and you're done.
14:46:13:Presenter: Any particular there is a theorem that says that the graph is already an if and only if all the vertices.
14:46:21:Presenter: Even degree in that connected. So you don't even have to compute it to know if it exists.
14:46:27:Presenter: Anne, okay, the next problem.
14:46:36:Presenter: It's DSP also known as the traveling salesman person. So I give you a graph.
14:46:41:Presenter: And I give you wait on the edges.
14:46:53:Presenter: Okay. And now looking for this might be two displayed people want this might be 7 3.
14:46:58:Presenter: And so on. So I give you this graph with the weight of the edges. Let's assume I'm going to do in this case.
14:47:02:Presenter: And the question is that I hamiltonian cycle.
14:47:04:Presenter: Is there.
14:47:10:Presenter: Five deciding a Hamiltonian cycle.
14:47:23:Presenter: Namely is there a way to go through the vertices of David it every vertex? Exactly once such that.
14:47:26:Presenter: The cost of the cycle.
14:47:34:Presenter: Is it most?
14:47:47:Presenter: I don't know. I'm fine, right? So the input is the graph G in a parameter alpha again to graph his weight on the edge as.
14:47:57:Presenter: And I'm asking is there are hamiltonian cycle that visits all developed it says shows that the total cost of the edges treated to the total weight of the edges with it.
14:48:07:Presenter: Is that what I'm for so this is a very if this is a very natural problem any particular?
14:48:18:Presenter: It has an interesting connection to Obama. So I don't know if you notice but link on the president make and president.
14:48:31:Presenter: He was a lawyer in Illinois and he was participating in this circuit court. So sickle to argue know, there are the local competition cottage one level above it.
14:48:41:Presenter: And in a way to Court Circuit Court is be cause what, you know this was the wild pretty wild at the time.
14:48:47:Presenter: So basically you would be that the code profit for one city to another, you know, from Springfield two.
14:48:54:Presenter: To Decatur. And so on. Every city that it would visit that would stop for a few days judge the case.
14:49:03:Presenter: The town move onto the next city in of course, what happened was that not only the lower not only the judge.
14:49:11:Presenter: We cover but the lawyers that you would also travel and then essentially, the judge in the lower would arrive to the town.
14:49:20:Presenter: Cases that were under dispute proved hire lawyers and they would judge this then that would go to court on this.
14:49:29:Presenter: The interesting thing is that we have the tools that those people did and the stores are optimized right? They're very close to being.
14:49:36:Presenter: The short that probably at the time because they were using wagons and stuff like that we're speaking about the job.
14:49:47:Presenter: 50 or maybe slightly before that since they will using wagon eternity or horses this problem was the closest cycle in the time.
14:49:54:Presenter: And the second call to the time had 7 pope's right. So it's clear that whoever decided on the circuit of the schedule.
14:50:03:Presenter: Solve this problem there optimization version. And in particular people solve this problem in real life, you know you have.
14:50:12:Presenter: Pop groups that goes on word two top Inter. T city or hundred cities and they try to solve such optimization problems.
14:50:21:Presenter: So this is probably the people who really care about in practice. So people walk to this point, work on Peace Peace.
14:50:31:Presenter: Although the computer science and, you know, in there are really bored application. So I feel good application effect include things.
14:50:40:Presenter: You have telescopes big telescope will you have to move them in this in the sky to take pictures.
14:50:50:Presenter: Of stars and which started to take picture of doing the night and you want to compute the minimized more minimum motion of the telescope to take all the pictures. So.
14:50:59:Presenter: There is a monstrous amount of research into this problem. There are books upon books working on that. And.
14:51:10:Presenter: At least part. Of course is NP complete and NP hard there isn't it cause, you know I can just take a graph?
14:51:22:Presenter: Right is. And so since I'm alone allowed to put weight on the edges, I might as well. Assume that they give you the complete graph.
14:51:28:Presenter: In edge is that they don't want you to allowed to travel and compute price infiniti on them, right?
14:51:33:Presenter: In all the other edges that can put price one. So deciding if there is a tail spin.
14:51:41:Presenter: This graph of price N is equivalent to deciding if there's a Hamiltonian cycle to do original graph before i did.
14:51:49:Presenter: The fake edges. So if we can solve hamiltonian speak it definitely solve a mystery and cycle and vice versa.
14:51:59:Presenter: So, well not quite vice versa. But that shows that, you know the problem is hard and effective.
14:52:16:Presenter: Complete. So this is DSP, let's see what's the next problem. I want to tell you about I can go like that forever. I'm just going to stay, I'm going to stop it sum.
14:52:23:Presenter: Point. And so the next problem that is funny set cover.
14:52:33:Presenter: It's kind of an abstract problem. So one needs to kind of not panic. Okay. When you see the problem.
14:52:42:Presenter: So it will be in this problems you read the definition that is this random sequence of notations and you have to understand what the hell's going on. So.
14:52:50:Presenter: So this is one of those problems. Unfortunately. So I would give it a concrete example. So the input.
14:52:57:Presenter: Use the pair in a parameter key, right. So let me give you the cook, it example 1 2 3.
14:53:08:Presenter: Form for this is S. You have a ground set in the second parameter is a subset of the set, so, for example think about it.
14:53:10:Presenter: 1 2.
14:53:14:Presenter: A 3 4 years ago whoops.
14:53:26:Presenter: So it's 3 4 and so on. Right. So F if I write formally if is a subset of the pot.
14:53:34:Presenter: Actually just subset is a set of subset of S.. So it's two to the S.. It's the power to subset of the powers of the face.
14:53:46:Presenter: And now your parameter K. Right. So you can now case would be two. For example, in the question is.
14:53:53:Presenter: Can I let me add some sets to each to make it remotely interesting which I guess it's too late.
14:54:01:Presenter: This case, but whatever one might only have almost at in this very capable two or three question is the following.
14:54:10:Presenter: I'm a bit K sets in S such a different take them together. I think the union be covered the ground.
14:54:20:Presenter: Okay. So that's the problem. This is the set cover. Maybe let me tell you about the geometric variant of this problem.
14:54:27:Presenter: I find more natural you've point think about them as customers. K.
14:54:35:Presenter: And houses in the cornfield and you have disks.
14:54:40:Presenter: Let me use a different quality of disks.
14:54:50:Presenter: Does this corresponds to the wireless company can put a base station at this point and it would save all the houses?
14:54:59:Presenter: In this side, and I'll give you a set of the risks, right, which is the candidates to the base.
14:55:06:Presenter: Haitians and then I can ask you can. So I can now ask you pin you give me four.
14:55:13:Presenter: This could cover all the points, right? Can you serve all those points with K base stations, right? So this is.
14:55:21:Presenter: Instance in action of the previous problem. Why is it interesting edge of the previous problem. Well think about just a ground set will be the point.
14:55:30:Presenter: Right to 1 2 3 4 5 right. So the count it will be 1 2 3 4 5.
14:55:37:Presenter: And F would be just for every bisque the set of points that can cover right in this case.
14:55:51:Presenter: B a new phone five is 3 4 2 3 4 and so on. Late, I guess that would be one.
14:56:02:Presenter: Okay. So this is very natural problem, right? The set cover problem is this cover is this problem is called clearly now.
14:56:09:Presenter: NP, right to give me a few 1006 in if you claim that the real solution of science.
14:56:17:Presenter: Can you can give me the case sets to the covering it just takes the union and verify that the covered the ground set.
14:56:24:Presenter: Like all the other problem with seen, so far it can be solved by brute force I can just enumerate over all possible.
14:56:33:Presenter: Subset of sized can't see check for each one of the solution for interesting explain shall time but I can do it.
14:56:49:Presenter: So this problem is clearly in NP is so by the cook live until we already know that, you know, if we can solve three SAT in polynomial time than we can solve this point in polynomial time.
14:56:58:Presenter: But they claim that we can already show that set cover is NP complete the reduction would be from what.
14:57:01:Presenter: You should know.
14:57:05:Presenter: Just guess at this point you should just guess.
14:57:09:Presenter: What the other problem we saw with the word covering it.
14:57:18:Presenter: Rockets cover, right? So if you look at vertex cover, right. So the claim is that vertex cover.
14:57:29:Presenter: Use polynomial with use a belt to set cover. Okay. So first I already argued that will fix the set cover is in NP.
14:57:41:Presenter: Right. And let's assume that they know. I know that vertex cover is NP complete rate. So put completed reduction to prove that set cover is NP complete.
14:57:47:Presenter: I just need to you to show that difficult subset covered probably term that they can solve vertex colors. So.
14:57:57:Presenter: A given an instance of vertex cover if they give you graph G in a parameter take in ask is the vertex cover of size. K.
14:58:05:Presenter: No two remind you. I said think about vertex cover and putting guards on the vertices to pick a guard.
14:58:16:Presenter: God told the edges in other words thinking about it is that every vertex cover all to edge is adjusting to it.
14:58:24:Presenter: So I'm going to do a bronc to create a set given the instant of vertex cover I want to create a new instance.
14:58:34:Presenter: The instance the ground set would be the edges of the graph in the subset of want to be the following, right for every vertex.
14:58:42:Presenter: For every let's see if we can write it in a way that makes sense. Let's call it.
14:58:44:Presenter: If we.
14:58:56:Presenter: Okay. What is F of V F which is going to be all the edges you've been in the edges of cough?
14:59:06:Presenter: You're right. So this is literally f of it's just all the edges are just in two.
14:59:15:Presenter: Me, this is already edge is that if we decide to pick V to mine vertex cover, this is all the edges that cards. So.
14:59:27:Presenter: You know, so vertex cover is just pick K guards which in this set cover languages just equivalent pick case X that cover all the edges of the graph.
14:59:35:Presenter: So the. So if we can solve vertex cover in polynomial time if you control set cover important end in itself, vertex cover.
14:59:44:Presenter: And that's it, right? So the problem is NP complete the proof essentially.
14:59:52:Presenter: And, of course, you know when you write down the proof. It's not much more slowly in more details, and so on. But.
14:59:58:Presenter: That essentially is the idea, okay.
15:00:10:Presenter: Welcome X appointment want to tell you about is that not one of the most fun problem.
15:00:28:Presenter: Subset son. So let's think about it, what is subset sum to give you numbers. Why not? So the number of going to be positive integer number.
15:00:32:Presenter: For the two integer numbers.
15:00:46:Presenter: Alright. So 7 16 34 500 you know in terms of water given a set of numbers that quality.
15:00:47:Presenter: Is.
15:00:53:Presenter: And then he via target number. T three is target.
15:01:06:Presenter: And question is the rest doesn't exist. This is the question doesn't exist subset X of the numbers.
15:01:12:Presenter: Such that the sum of all the number in the set.
15:01:29:Presenter: Is equal to one not 1 1 will be easy two easy equal to three. Okay. So assumption summer ask, you.
15:01:34:Presenter: Is there a subset of the number that ends up exactly to the number of people care about?
15:01:41:Presenter: In this problem is in NP. Of course, again, you can just give me the subset that realized the sum.
15:01:52:Presenter: And it could be solving exponential time by enumerating all subsets. So this problem in this problem is NP complete.
15:02:05:Presenter: What makes this problem interesting is that this problem becomes hard only if the numbers of very large. So.
15:02:15:Presenter: If I give you N numbers. So maybe let me try to say what I mean by that, so that proof of this which I'm not going to go into because it's.
15:02:23:Presenter: Again a messy but it in the class not. So the reduction is from three SAT into subset sum.
15:02:39:Presenter: And basically deer is that if we give you a formula with end variables in.
15:02:43:Presenter: In clauses.
15:02:53:Presenter: What the reduction does there is a reporter mental reduction, and it's going to generate something like in plus in numbers.
15:03:00:Presenter: But the numbers are going to be huge the numbers are going to each one roughly implicit in bits.
15:03:08:Presenter: Okay. So not, if I am in a large death the not the numbers are very large.
15:03:15:Presenter: And then you don't do carefully argue that and you compare for computer target tambourine you argue that there is a subset sum.
15:03:23:Presenter: The numbers if in only there is satisfying assignment and vice versa it is fun proof for the right value of five.
15:03:34:Presenter: And which is not very good value? And so in other set it in the cluster people look it up.
15:03:41:Presenter: It's interesting that some level in but the question of courses.
15:03:51:Presenter: Do we really need large numbers? And it turns out the answer is yes. So in particular is the theorem?
15:03:58:Presenter: Which we might see later in the clue in the class, if I have a subset of numbers.
15:04:02:Presenter: Set of numbers.
15:04:06:Presenter: Point.
15:04:16:Presenter: Integers positive. And so on. And we have a target. T number of T set of numbers, then this problem.
15:04:20:Presenter: Can be solved in.
15:04:35:Presenter: One has to be careful in tee time, okay. And this is socially astonished dynamic programming solution. It's a simple example of dynamic programming.
15:04:43:Presenter: So you can solve this problem in end times t time where P is the size of the target number.
15:04:50:Presenter: But you don't have to target number has 10 plus impedes the value of tears point to be you know.
15:04:57:Presenter: Something like two to the end plus M roughly, it's going to be monstrously large. So this is not a polynomial time.
15:05:07:Presenter: But not at hand if these small, then you could solve it sufficiently, okay. Any particular one of the theories.
15:05:14:Presenter: In this class can simply knows what a very nice paper about how to solve it faster than this.
15:05:21:Presenter: In expansion time in the worst case but better than this. So this is kind of stuff that people who could.
15:05:28:Presenter: Okay, subset term is in, I don't hold version of this problem is the partition problem.
15:05:43:Presenter: Okay, fish. And so the partition is the same thing I give you a set of numbers integer positive numbers of numbers.
15:05:50:Presenter: And the question is can I split them into two sets.
15:05:53:Presenter: So.
15:06:04:Presenter: Or maybe I should not try and this can I partition them into two sets one units two equal to.
15:06:12:Presenter: Yes, I'm going to abuse notation and use this for disjoint union. So I picked the set of number.
15:06:21:Presenter: Every number I started to the left to do the right side is and I required the sum of numbers in. S one.
15:06:24:Presenter: Is equal to the sum of numbers.
15:06:30:Presenter: A, a short interest or.
15:06:40:Presenter: Those two sums are equipped. So you stayed away to partition the two sets to be equal and reduction is not very difficult reduction from subset sum.
15:06:50:Presenter: Going to buy bitters and clear again, this problem is NP given a partition, you just need to tell you for every.
15:06:55:Presenter: Number whether it will be left her the right side, and it can easily verify it. So the problem is in NP.
15:07:01:Presenter: Okay, subset sum partition bin packing.
15:07:09:Presenter: So been talking about two kind of describe the easiest variant by the way, I should say that all the problems.
15:07:17:Presenter: I mentioned there are more and more complicated versions usually, I'm trying to, I'm telling you the simplest version.
15:07:26:Presenter: That is NP complete bin packing to give you numbers this want with N again positive integers. Blah? blah.
15:07:36:Presenter: And I give you be which is bin size bars and I guess I think I would have to parameter take.
15:07:44:Presenter: Right. So the way to think about it think about every number as the size, right in the *** just a container.
15:07:53:Presenter: That can contain up to be unit of stuff, right in there, it is that you want to split down the number input.
15:07:58:Presenter: Okay, groups such that every group feet in a bit.
15:08:06:Presenter: Okay, in the use of this thing is completely not true. I just think about things like file systems.
15:08:16:Presenter: Right. So more than five system have to think where if you create a tiny file. It's not stored in its own block it shared.
15:08:23:Presenter: It might be several files showing it store in the same block and then you want to for example use the minimum.
15:08:31:Presenter: Block for the five you head, right. Or I just said you want to send things in containers.
15:08:39:Presenter: Right. So you want to solve. So any question here. For example would be for this instance can you partition the number two.
15:08:48:Presenter: Case K set such as everyone of them fit in a bit. Okay. So this is bin packing and.
15:08:50:Presenter: I think.
15:08:57:Presenter: Okay. Please two more problem. I want you to tell about it. If I have time to tell you about them.
15:09:01:Presenter: So the next problem is three coloring.
15:09:07:Presenter: Yeah.
15:09:20:Presenter: No bees usually fixed. So usually few optimize, okay. The more complicated version in every item has a price.
15:09:28:Presenter: Which is how much money you're getting paid? So you know, you and your feet given K and you want to find a million.
15:09:38:Presenter: You know, the subset you want to pick which item to put into the bin such to maximize the amount of money you pay.
15:09:46:Presenter: You get paid big difference. So but, it gets more and more complicated that goes in real life.
15:09:57:Presenter: If those item are three dimensional think about Amazon delivery. Okay. And you want to optimize the space in the book in the container, right? So.
15:10:05:Presenter: You don't want to just have a tiny box rounded by huge amount of packing material like Amazon does.
15:10:15:Presenter: So you H don't be Amazon, okay, three colors, I give you a graph.
15:10:25:Presenter: And they ask you can be colored by three columns. This is a kinder garden question. And so here we are coloring the vertices.
15:10:39:Presenter: So three coloring means we assigned to vertices three colors. And this case, for example, that will be a valid three coloring.
15:10:48:Presenter: Where the whole of the game is that we are not allowed to put the same colors on an edge right. So all every edge must have.
15:10:57:Presenter: Three different colors, and the question is can be graph be colored by three colors. So, of course, the two coloring version.
15:11:07:Presenter: In Italy. I ask is to graph can the graph be colored with pick two colors, and then take the most natural algorithm just walks.
15:11:16:Presenter: Right. You start to vertex you color it by 1 4 then you colored the other end point by different color.
15:11:22:Presenter: All right. And you repeatedly do it, right? In fact, the right way of thinking about it take a vertex.
15:11:31:Presenter: Assume the graph is connected take the graph to peer computer BFS three of the graph called to order levels of the BFS trip.
15:11:43:Presenter: One corner and even want by that'd color in number just check if there is any edge. That is between two vertices of the same color in the graph is not too colorable.
15:11:50:Presenter: Otherwise, it is the reason the proof is just what I said, I think you have two colors everything is forced.
15:11:58:Presenter: So if you have an invalid edge than just not run it an three coloring on the other hand.
15:12:09:Presenter: Is NP complete? So again, it's the problem is clearly NP you can easily verify the coloring. So that's good.
15:12:19:Presenter: And in the gate there is a reduction, I think it's what yes. There is reduction for peace at.
15:12:28:Presenter: It's in the lecture nodes again. It's one of those very clever reduction with gadget and stuff, you can look on the slide of the classroom.
15:12:37:Presenter: You see it. I'm not going to go into details here. Let me say by the way that all problems.
15:12:47:Presenter: You know, all the parliament discarding their how but somehow there been others. So here's a version of this problem.
15:12:55:Presenter: If you graph I tell you. It's three colorable. I just ask you to color it how difficult candies.
15:13:03:Presenter: B. Okay. So this already turned out to be extremely hard, in particular, if it if you graph intelligent two colorable.
15:13:10:Presenter: Currently don't think we know how to do in polynomial time is to coloring for something like, you know.
15:13:16:Presenter: With this type. Of course, I don't remember the exact thing but it some polynomial in N, right? So.
15:13:20:Presenter: I tell you the graph can be colored in pre colors and the only thing we know how to do efficiently.
15:13:33:Presenter: Credibly by with a monstrous number of colors. So that's kind of fairy chorus and, of course the famous theorems that was proved Indiana.
15:13:43:Presenter: You only see the math department is that all planner graphs can be four called. So planet of the graph we can draw it in the plane.
15:13:49:Presenter: Vertices of point and you collect every two vertices based care of in two curves are not allowed to cost.
15:13:57:Presenter: What planet of can be colored by four colors? So this is the one of the main resort about graph coloring.
15:14:04:Presenter: Okay. Let me mention one final problem. And that would be the end of the lecture hitting set.
15:14:18:Presenter: So hitting SAT is literally the dual problem of set cover. So I give you a ground set. S.
15:14:29:Presenter: And collection of sets f, right in a parameter K in the question is there a subset of the elements.
15:14:41:Presenter: Of science. K such that for any set in S in F three. So I look at every one of my set.
15:14:45:Presenter: And everyone of the set contains some element of X.
15:14:48:Presenter: So.
15:14:59:Presenter: Okay. So you could pick K elements such that every set contain one of your elements. And as I said, this is actually equivalent to eating set.
15:15:09:Presenter: You can think why it's true that the reduction with the relatively easy. Thank you very much. There is a discussion section at fault.
15:15:13:Presenter: Thank you.