In the previous unit, we have introduced the notion of NP completeness and seen that a myriad of practically relevant problem is NP complete. So, we think there is no polynomial time algorithm for these problems. Now, the question last time we left off was what does this mean for Alice, Bob, and Carol--the three computer scientists we were following? Should they just give up? Should they ask for a new problem? And I think that is something they might do, arguing that the problems are NP-complete, but actually they could do much better, using some of the techniques that you are about to learn in this unit and the following units. Because what we will now be investigating is techniques to actually solve problems despite their NP-completeness. Now, this will not always work, but it will be much better than just giving up, because there are so many NP-complete problems out there that are just too practically relevant to leave them alone.
In the previous unit, we have introduced the notion of NP-completeness. We have seen that many practically relevant problems fall into this category, such as vertex cover, clique, independent set, and of course the SAT problem that we got to know in the last unit. Now, since the famous P versus NP problem is unsolved, there is no algorithm for any of these problems that is guaranteed to run in polynomial time. Now, in the first unit, we met three computer scientists who were working on these problems, and they did not know that their problems were NP-complete. So, in this unit, what I would like to teach you is how you can detect that a problem is NP-complete. Then in the following units, we'll be dealing with counter measures. Once you have found out that your problem is NP-complete what can you do about it?
So, in order that you save a little time compared to Alice, Bob, and Carol, our first quiz this unit is going to be what should you do when you can't find and polynomial time algorithm for some important problem that you're working on. Here are your options when you can't find a polynomial time algorithm for a problem you're working on. You can do some research on the problem. You can try to show that your problem is NP complete. You can give up right away. You can discuss the problem with friends and possibly also experts if they are available to you, and you might also think about settling for a suboptimal algorithm-- some algorithm that works but probably doesn't produce the best possible solution, at least if the stakes aren't high. So, which of these options do you think could be recommended in general?
All options except for giving up immediately are viable options depending on the situation. So it's always a good idea to do research on the problem that you're working on because many problems that occur in practice have occurred elsewhere before. So it's likely that there will be some research on this problem, and that can help you a lot potentially. Of course, you can also try to show NP-completeness for your problem because if you manage to show this, then you know your problem is going to be hard. This is not an excuse to give up right away, but you basically just know what you're dealing with. It's always a good idea to discuss the problem you're working on with friends and experts, of course, because they might have a new insight that helps you. And finally, settling for a suboptimal algorithm--and we're going to talk more about this in later units--can sometimes also be a good option if the stakes aren't high. So, for example, Alice working on vertex cover--if her company is happy with installing a few more monitoring devices than the absolute minimum, then she can possibly find another algorithm or just maybe even solve it by hand if she wants to. In this unit, we're going to focus on this aspect here-- showing you how you can prove NP-completeness for a problem. We have already done this a couple of times, but it's worth to practice this technique. And then how you can do some research on your problem. So I'll give you some example problems that often occur in practice so that you know the names; and when you come across them, then you'll have an easier time to find out more about the problem that you're trying to solve.
In principle, of course, you know by now how to show that a problem is NP-complete because we have already shown this in the last unit for 4 different problems. We have shown the NP-completeness for vertex cover, we have shown the NP-completeness for clique, we have shown the NP-completeness for independent set, and then for SAT, the mother of all NP-complete problems if you will. So for showing NP-completeness, there is always 2 steps. First you have to show that your problem is in NP, which means that a nondeterministic RAM can solve your problem in polynomial time, and later in this course we will meet some problems actually that are worse than NP-complete problems, so it's often a very simple step, but it's one that you have to go through because you might be dealing with even harder problems although that is unlikely. And the second step was finding a polynomial time reduction from another problem that is known to be NP-complete using the ideas that Cook and Levin had for their famous Cook-Levin theorem. Then we showed that clique is NP-complete by reducing SAT to clique. And then from our first unit, we already knew that clique, vertex cover, and independent set are all very closely connected to each other. So you can basically reduce these problems to each other in any order or way that you want because they are so closely related. I would like to do a brief quiz with you, which is a little bit subjective although I think you'll likely agree with me, and what I would like you to tell me is how difficult you found those reductions that we have encountered so far. So showing that SAT is NP-complete, showing that clique is NP-complete, and then showing that vertex cover and independent set are NP-complete, and I would like you to rank these where 1 means easiest, So please rank the difficulty of those reductions that we have encountered so far.
Now, of course, this is a little bit subjective, but to me, it's clear that showing that SAT is NP-complete was the hardest thing that we had to do because we didn't know any other problem to be NP-complete, so we had to go through a lot of effort to show that any problem in NP can be expressed as a boolean formula for SAT. Then I think that showing clique to be NP-complete was the next difficult thing because it's not really obvious how you can reduce SAT to clique because SAT is a problem on boolean formulas; clique is a problem on graphs. And so we had to find a good idea to show how SAT can be reduced to clique. And then, in the first unit, it still took some thought, but showing how vertex cover, clique, and independent set are related wasn't that difficult because all three problems were asking questions about graphs, and they were asking mostly very similar questions, especially clique and independent set. Vertex cover--yeah, we had to give it a little thought, but I still think it was much easier than coming up with the idea of how to encode a boolean formula into a graph that is then an input for clique. So the good news is the hardest part is over, but, of course, as you've seen with SAT and clique, showing NP-completeness can still be tough. And that is why I would like to show you one more example of a reduction for a quite-famous NP-complete problem that you don't know yet and then give you some more general strategies on how you can show NP-completeness for other problems. And to introduce that problem to you, I would like you to meet Dave.
So Dave is also a computer scientist just like Alice, Bob, and Carol, and he is working in Logistics, and the problem that he is working on is optimizing the delivery routes for the mail trucks of his company. So basically, the problem that Dave has to solve each day is the following: Here's the headquarter of his company where each day, the mail arrives, so maybe the mail arrives by an airplane, and that airplane delivers letters each day, and then this delivery truck here has to deliver those letters to all of the houses that receive mail that day. So let's say it's those 7 houses here where this truck has to deliver the mail. Now of course, the roads that connect the houses, so not every house is connected to each other house directly, and the roads also have different length, and I'm going to specify this in minutes, so if I write a 40 here, it means you need 40 minutes to get from this house to this house, and then 14 from this house to this house, and 13 from this house to this house, and so on. So you can already see that this looks very much like a graph except that the edges now have a certain distance or time attached to them. Now the problem that Dave has to solve is a problem that we will call shortest tour. We will say that as an optimization problem for now, we will later work with the decision problem to show NP completeness of this problem. The truck starts out here at the headquarters, and then, Dave is supposed to figure out the fastest way for the truck to visit all houses and then get back to the base, so it starts out here, has to visit all houses. It can visit a house more than once, in case you're wondering, and then it has to get back to base. So let's say the truck starts here and let's say the first road it takes down is this one here. What I would like you to tell me is in which order should the truck visit the other houses? So this is the first house that the truck is visiting, and I want you to enter a 2, 3, 4, 5, 6, and 7 here, so if the house travels from House 1 to House 2 then to House 2 and so on, it's taking the fastest possible route to visit all houses.
And luckily there's not many houses here, so a bit of playing around, I think you can get it. So first, you have to take this long road over here, because any other way to travel over here is much longer and then you still need to go back, so with a bit of playing around, you can find out you can find out that the next house to visit is this one here. Then it's almost obvious that you should go up here. Now here, you can choose to take the fast way to this house up here or the one that takes a bit longer; actually, it's better here to go down, because otherwise, you'll have to visit some of these houses multiple times. Then you can go back up here, and then you go over here, and then it's almost obvious, because you have to drive to base, anyway. That--this is the last one you have to visit, and then you go back to base, and the total time for this is, and I calculated this for you as a service,
So Dave has the same problem that Alice, Bob, and Carol also had. If he uses a simple or a naive algorithm to solve shortest tour, then this algorithm will not deliver an acceptable running time, because what a simple algorithm would do to solve shortest tour is that algorithm would simply try all possible orderings for the houses. So, what I just asked you to fill out in the last quiz, the computer would just go through all possibilities of saying this is the first house to visit, this is the second house to visit, and then go to the following house as the 3rd house, and so on. So we have not even needed to go deep into the details to see that this algorithm will quickly fail once the number of houses grows, because the number of possible orderings here will grow enormously with n where n is the number of houses. So, let's do a little quiz to make this more explicit. So, what I would like you to tell me is if we had 5 houses to visit, not counting the base we start from and get back to, but 5 houses where we can decide in which order to visit them, how many ways are there to visit 5 houses, and then how many different ways are there to visit 10 houses. You are going to need a program or calculator for figuring out at least the second one; the first one you can probably do in your head, but for this one you already need the computer to calculate the number.
So the answer here is, there are already 120 possibilities to visit 5 houses. The way you calculate this is there are 5 possibilities for the first house, times 4 possibilities for the second house, times 3 for the third one, times 2, times 1. So it's the same as a factorial of 5, if you are familiar with that terminology, which is 120. For the second one, the number in different ways of which you can visit 10 houses, it's a factorial of 10, which is precisely 3,628,800. As you can see this number here grows enormously. Just to give you one more example. If we were to visit 15 houses, then the number of possibilities would be 1,307,674,368,000, which, as I'm sure you'll agree, is quite a lot. Even for a computer to handle.
Now as you'll remember from the last unit, just having a huge number of potential solutions of course does not show that your problem is NP complete. But it can be an indicator if you cannot come up with any substantially better algorithm. Dave currently cannot come up with a substantially better algorithm, so he wonders could his problem of shortest tour also be NP-complete? That's why, together with Dave, we will now try to show that indeed shortest tour is NP-complete. To do that we will go through these 2 standard steps here. First of all, we have to show that the problem of shortest tour is in NP. To do that, as you'll remember from the last time, we actually have to state this problem as a decision problem. So here's our next quiz for you. How can Dave state his problem of shortest tour as a decision problem? Given a graph with distances, what is the shortest tour? That visits all vertices of course. The second option would be, given a graph with distances and a number d, is there a tour of length at most d? Given the graph with distances, how long is the shortest tour? Please check the problem statement that states shortest tour as a decision problem.
As you'll remember from the last unit, a decision problem states a problem in a way that the answer is either yes or no. It cannot be the first one, because what is the shortest tour would actually have to specify that tour. It can also not be the third one, because given a graph with distances, how long is the shortest tour, that asks for a number. The only yes/no question is the second one here. In order to state shortest tour as a decision problem, we have the graph wtih distances as an input and a number d, in order to be able to ask if there is a tour of length at most d. This one here is correct.
So now that we have shown how shortest tour can be stated as a decision problem, we still need to show that that problem is in NP, and for shortest tour, while it's not really that difficult, but it's actually a little bit of a hassle, so let's do another quiz here. Why is shortest tour in NP? So basically the question is: If we have nondeterminism, why can shortest tour then be solved in polynomial time? Is it because we can use nondeterminism to guess which vertices to put into the shortest tour? Is it because once once a shortest tour has been guessed using nondeterminism, the length of that tour can be checked in polynomial time? Is it because nondeterminism can guess a shortest tour, and by that I mean that we can use the better function to guess the tour here, so you would have something like this: if better visit vertex A, else visit another vertex next. Or, do we even have to show this? Because, actually, it's quite obvious. So, more than one can be correct. Please tell me which ones are.
And there are 2 correct answers here. One is that we can use non determinism to guess a shortest tour. It's not totally obvious how to do that, because the if-better function always can only do 2 distinctions, so you have to find a clever way to use that function to guess how to construct a shortest tour, but it's possible in the way that I've showed you here. Then once the shortest tour has been guessed, checking if the length is shorter than D, and as you'll remember, D was the maximum length that we allow for it, because we are having shortest tour in the decision problem. Once the shortest tour has been guessed, it's easy to check if the length of that tour is smaller than D, so by easy, I mean it's possible in polynomial time, so this one here is also correct. Non determinism can be used to guess which vertices to put in the tour is--obviously doesn't make sense, because all vertices are part of the tour. It's the order of the vertices that matters for solving shortest tour. And then the final one, of course, that was easy to see that it's not really a viable answer, but I wanted to point out to you that even though it might sometimes be obvious, you should always make sure to explicitly show that the problem is in NP, and we'll actually, later in this course, come across some problems where you might initially think that they are in NP but actually they're much harder than problems that are in NP. So now, we have completed the first step. We know that shortest tour is in NP and now consider finding a polynomial time reduction from an NP complete problem to show shortest tour is NP complete.
Now, before we actually do step two, let's have a brief review of what step two actually means. So, to show that shortest tour is NP-hard, which would then make it NP-complete, because we've already shown that it is in NP, what do we need to show? Do we need to show that the input for some NP-complete problem can be transformed into an input for shortest tour. And, of course, if this input here is a yes for this NP-complete problem, then it has to be yes for shortest tour here as well. If it's the no it's has to be a no. Or do we need to show that the input for shortest tour can be transformed into an input for some other NP-complete problem? Basically, I would like you to review here which direction these transformations work. Of course, we'll always make the assumption that the transformation is in polynomial time.
And the correct answer, if you remember right from the last unit, is that we need to take some NP-complete problem and show that we can use shortest tour to solve that problem, so, this one up here is correct because, as I told you, a reduction basically means that we show that this NP-complete problem here, and we still have to choose a good one, kind of fits into shortest tour, so shortest tour is at least as hard to solve as this one up here. If it were the other way around, then you would just show that this NP-complete problem is at least as hard to solve as shortest tour, but that doesn't give you any statement about shortest tour, so this is the way we need to do the reduction. Now, it says some NP-complete problem here, so the question of course is: Which one is it going to be? Later in this unit, I'm going to show you a bunch of resources that you can use to find suitable NP-complete problems to do your reduction, because when you have a very similar problem, and that's what you've seen with vertex cover and independent set, then the reduction becomes much easier to do. We saw with SAT and clique, for example, that, if you have problems that are a bit different, then you might run into trouble. So, I'll give you those resources, but here's a general rule. If you don't find an NP-complete problem that is very similar to the one where you're trying to prove that it is NP-complete, then usually it's a good idea to start with SAT because SAT is in a way a very flexible and very universal NP-complete problem, so that's exactly what we're going to do here as well. We're going to try to reduce SAT to shortest tour.
So how would we go about to reduce SAT to shortest tour, or how do you generally go about showing NP-completeness when the 2 problems that you have are not related to each other? So let's briefly just restate what the SAT problem is and the shortest tour problem, and then let's try to relate the 2 to each other. SAT was a problem where you were given as input a Boolean formula, and the output or question was, does the formula have a satisfying assignment? And of course that is a yes or no question because we're dealing with a decision problem here. And shortest tour, that's easy to remember because we talked about it a lot so far in this course. The input was a graph with distances, and we said we need a number d in order to make this a decision problem, and the question here was, is there a tour of length at most d? And by tour we mean that we want to visit all vertices at least once, but we can visit them more than once. So now comes the creative part. How on earth are we going to take a Boolean formula and turn this into a problem related to mail delivery? And it's not obvious. So what I always find useful to do in these cases is to just write down all the properties that a Boolean formula has, that a satisfying assignment has-- so anything I can think of for SAT-- and then write down properties of the shortest tour problem and see if I can find a certain relationship between them, because oftentimes that will give me an idea of how to accomplish a reduction like this. So let's see. Properties of SAT. The first one is each variable is set to either true or false but not both. So it's either true or false. And these are all trivial properties, but let's see if they help us. And actually, deciding whether a variable should be true or false is what makes this problem hard. So I can also write that down. So deciding this true or false for each variable is what makes SAT hard. Then what you will also remember is that when we talk about a Boolean formula, then we can write it in conjunctive normal form, which is this form here where we have a bunch of variables that are combined by an or and then brackets around that, then comes an and and then comes again a series of ors and then comes an and and so on. This part here we learned in the last unit was called a clause. So first of all, if there is a satisfying assignment, each clause must be satisfied. So how do you satisfy a clause? Since in a clause, as you remember, we just have ors between the variables, this means that 1 single variable, if it's set in the right way-- so either to true or to false if we have a variable with a not-- then setting 1 single variable the right way is enough to satisfy that clause. And so we should probably also write that down. One variable is enough to satisfy a clause. Let's see if we can do the same thing for shortest tour. What are some properties of a shortest tour? First of all, every city must be visited at least once because otherwise it's not a valid tour. The main decision we need to make is of course in which order we visit the city. And once we have visited a city, we can visit it again but we don't have to. And the final thing is we don't visit a city more than once on purpose. So at a certain point in time we might want to visit a city once more because it's beneficial, but in the shortest tour we wouldn't visit a city more than once unless it's necessary. So I'm going to phrase this as we don't visit a city more than once on purpose. Now, you might be wondering why I have left the numberings here blank, and that is because we are now going to have a little quiz here, because what I would like you to think about is here we have 4 different properties of SAT and here we have 4 different properties of shortest tour. I would like you to find out which properties of shortest tour are most closely related to these properties here of SAT. This is a bit tricky and subjective, but I think it's very valuable to learn this style of thinking. So before you hit Next out of frustration, please at least spend a little bit of time trying to figure this out, and then enter here the number that you think most closely corresponds over here. So if I were to say that deciding true or false is what makes SAT hard is a close analogy to every city visited at least once, I would enter a 2 here. But this is actually not a correct answer. And also I have structured it so that each number here will only appear once. So how are these 2 related?
As I compare these 2, I would say that Every city is visited at least once sounds like each clause must be satisfied, so we must basically ensure that our satisfying assignment satisfies it at least once, so I think this one here is closely related to this one down here. The main decision is the order in which to visit the cities. That is what makes this problem hard and the analogous decision that you have to make for SAT is deciding which variables to set to true or to false, so I think these 2 are quite closely related. Then being able to visit a city more than once but not having to do so. I think that is closely related to number 4, because what we have here is one variable is enough to satisfy a clause, but of course, we can use more than one variable to satisfy the clause; it doesn't hurt if there's more variables here that will evaluate to true, so we can satisfy a clause in multiple ways, but we don't have to; one single variable is enough. And ten finally, saying that each variable is either true or false. I think--and this is probably the hardest one to figure out-- and that is actually quite closely related to saying that you don't visit a city more than once on purpose. It means you basically have to make a decision what city to visit next, and that is, in my mind, more or less close to saying I'm setting a variable to either true or false. Once you go along the shortest tour, you're always on your way to a new city, but again, I realize this might be a bit subjective here. Let's use this relationship to try and reduce SAT to shortest tour, and I think we should start out with this relation here. Deciding true or false is what makes SAT hard. The main decision is the order in which to visit the cities. So the important insight here is that if we should try and find some way to represent true or false as an order in which cities are visited and to assure through that order also that you cannot have ambiguous assignment of true or false, so basically, you have to make a decision in which order you visit the cities and that much represent either true or false and to figure this out, of course, that takes a lot of playing around with different networks, so even though I had learned the proof, I didn't quite remember how to do it, and it took me 15 or 20 minutes to play around on a piece of paper with a pen to find out how it could represent true or false variables as an order in which cities are visited, and there's many possibilities, but I'll show you what I came up with and then explain that to you.
So, I'll start out with a very simple graph here. Let's say in this graph you wanted to get from A to B. I've purposefully not added any distances to the edges here, because we will just assume that the length of each edge is 1. Now, if you wanted to get from A to B, what would be the length of the shortest path from A to B that visits all vertices. Please enter your answer here.
And the answer here is 7, so one example would be 1, 2, 3, 4, 5, 6, 7.
Now, how many different shortest paths are there from A to B? Please, again, enter your answer here in this box.
The answer here is that there are 2 different shortest paths from A to B. Starting out at A you can either go up here, then down here, then up here, then down here, then up here, or you can go down here, up here, down here, up here, down here. There is no other possibility of getting from A to B while visiting all vertices and only taking up 7 edges.
Now let's draw this a little bit longer. Again I'm going to ask you 2 questions here. The first one is again that I would like to know from you the length of a shortest path from A to B that visits all vertices. Please enter this here in this box. I would also like to know from you how many different shortest paths there are from A to B. I would like you to enter your number here in this box.
And the answers here are that the shortest path from A to B has length 10, so, for example here, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, and the number of shortest paths from A to B is still 2. If you start on A, and once you've made the decision to go up here, the only way to continue the shortest path is like this, because otherwise he would be visiting a city more than once, and then the path gets longer than 10 edges. If, on the other hand, you start out by going down, then there is no other way to go along the shortest path than this here. So again there's 2 diffferent possibilities of going from A to B along the shortest path that visits all vertices, and the length of that shortest path is 10.
Now I am very sure that you have figured out a pattern by now, so let's draw a really long one. Of course, I'm going to ask you the same questions, but this is the last time I'm going to ask you those two questions. So, please once more, what is length of the shortest path from A to B? And what is the number of shortest paths from A to B? By shortest path, I mean one that visits all vertices, as in the examples before.
The answer here is that the shortest path from A to B that visits all vertices has length 19, so 1, 2, 3, 4, 5, 6, and so on. You can recount if you don't trust me by now. The number of shortest path from A to B, that again is 2. So having these 2 possibilities of a shortest path that visits all vertices from A to B either going this way or going this way. That is in some way very similar to setting a variable to true or false, isn't it? Because, if I want you to go from A to B as quickly as possible while visiting all vertices, then there are only 2 choices that you have. The interesting thing is that, in one of those choices you always take the edge that goes from bottom left to top right, so this one here, this one here, this one here, and so on. If you start out by going down right, then this is what you will do at any other edge here as well. There's no shortest path between A and B that mixes up these 2 possibilities, so that takes some of these edges here and some of these edges here, and this is exactly what we're going to use to represent a variable being set to true or false.
So what I'm now going to do is--I'm going to take the structure here, make it a bit smaller like this and take away the NP here, and we are going to reappear in a minute. What I'm now going to do is I'm going to put a bunch of these structures together. So connect this one edge, connect this one edge, and we're also going to do one here and now call this one A and this one B. Now, what you see here is that I have taken three structures like these and put them between A and B. I'm going to do this more generally now. Imagine that instead of an edge here, I could have more of these structures. I'll just write three dots here and these will represent additional copies of this structure being in between here. So in total, I will have n copies of the structure--n times this structure here appears between A and B. And now my question is, how many shortest paths between A and B can you have that visit all of the vertices here. If you have n copies of that structure, is that nÂ², is that 2^n, or is that 2n.
The answer here is that if you have n copies of this structure here in a row like this then there are 2^n different shortest paths from A to B that visit all vertices. And the reason why that is is that each time you encounter this structure here there is the two possibilities that we talked about. You can either go this way up here or you can either go this way down here and then you have to continue this way until you get to one of these edges here and then you can redecide if you want to go up or you want to go down. There's two possibilities for the first one, two possibilities for the second one, and so on and so on and so on, and two possibilities for the last one. Two multiplied by itself n times is 2^n. And this actually doesn't look too bad, does it? Because each of these gadgets, if you will, that I've drawn here could now represent a variable in a Boolean formula and each shortest path between A and B is kind of a true-false assignment to those variables. We could say for example that whenever we choose our path from A to B to go up here and then like this, this structure here or this way to do the path. Now that represents setting the variable to true so this here which represents xâ‚ for example so then going this way would mean xâ‚ is true. Going the other way, so down, would represent false. This would be a way to represent assignments of true and false to the variables xâ‚, xâ‚‚, and so on through xn. Now of course choosing the path between A and B is still totally arbitrary. What we are missing is the clauses of the Boolean formula. And again it takes a bit of playing around to find out how we can represent clauses here in this picture.
To figure this out, let's have a look back at our picture from before. We said that in a set formula each clause must be satisfied and set this is kind of similar to the requirement that each city must be visited at least once. This would suggest to add some additional vertices to the picture that represent clauses. So let's say we have one vertex here that represents clause #1 and another vertex here for clause #2 and so on. What we could say is that visiting this vertex here represent satisfying that clause and then of course, we need to make sure that we can only visit the city here if the corresponding variable or if one of the corresponding variables of that clause is satisfied in the right way. What about a construction that looks like this--I connect the vertex that represents the clause to this one here and I connect it to this vertex here and I connect it to this vertex here. What I would like you to think about now is the following, there are 2^n shortest paths between A and B if we do not regard this vertex here. If we do not have clause 1 and I realize it's not the best name for that vertex but that's okay. If we have to visit this vertex here, so it's now become part of our graph. How many shortest paths from A to B do you have then that visit all vertices. Is it still 2^n, is is 2^nâºÂ¹, or is it 2^nâ»Â¹.
Now comes the interesting part because the answer is 2^nâ»Â¹. The important thing to notice here is the following. You still have two possibilities of visiting this part here. So there's still two possibilities. And you also have two possibilities for this part here and all of the other ones in between as well. But here something interesting happens. If we choose to travel up here then down here then it cost us one extra edge to visit clause #1 as opposed to if we had gone from this vertex here to this one directly. Just one extra edge. Now what would happen if we go down here? If we were to visit this vertex immediately then we are over here, which means we haven't yet visited these two vertices here so we need to go backwards, then up here, and then back. Something like that--so this is not going to be a false path because we're starting to visit cities multiple times and even if we tried to do it another way so maybe just visit this here first then we can't go down here again because then we would again visit cities twice. Also going over here, then up here, then backwards through this and also revisit this city here twice. What you can see is that on a shortest path if we want to visit this vertex down here then we must take this route. If we do not have to visit this vertex, then we don't have to take this route then we can still chose arbitrarily. The number of shortest paths between A and B, if we have to visit that vertex, has been reduced and that is pretty neat because that means we can only visit this vertex here on a shortest tour if we are going the right way and now you can already see the relationship. If we connect this clause here to this part here, which represents a variable in the right way so that we can only visit this city if the variable is set in the right way because we said going up here means true, going down here means false, then we can ensure that a shortest path from A to B visits this vertex here, which means that we can also have a satisfying assignment for this clause here. And I'll illustrate this for you in more detail.
Let's say we build a graph like this. We have a structure that represents the variable xâ‚. We have a structure that represents the variable xâ‚‚ and a structure that represents the variable xâ‚ƒ here, and we have a clause that say, it goes like this--xâ‚ or not xâ‚‚ or xâ‚ƒ. And what we said with regards to the past between A and B, we said that going this way means true and going this way means false. So what we'll do now is we have xâ‚ here in this clause, we will connect this vertex over here and over here. What that means is that we can visit this vertex here for just one extra edge as long as we're taking the path--that means xâ‚ is true. Here, this is not right because we have not xâ‚‚, so we have to connect it in another way-- we have to connect it in exactly the reverse way because then when we take the path that means xâ‚‚ is set to false, then not xâ‚‚ becomes true and again, in that case, we would want to be able to visit this vertex here for just one extra edge. Now, my question to you is--how would I have to connect this vertex here to this part here of the graph that represents xâ‚ƒ. Would I have to connect it in this way or would I have to connect it in this way. Please check the one that is correct.
This case here is correct for the following reasons, xâ‚ƒ is just as it is--there's not a not. What that means is that if we take the path that signifies xâ‚ƒ is set to true and we know that is the path that goes like this. Then we want to be able to visit this vertex here by paying so to say just one extra edge, so that's exactly this one here. If we had not x3 here, then this answer here would have been correct. It seems like this is actually a good idea to show that any Boolean formula can be transformed into a graph such that the shortest path between A and B tells us whether the original Boolean formula had a satisfying assignment or not, but of course we haven't proved it yet and that is why we will now have to go into gory details in order to actually prove that we can reduced SAT to shortest tour.
We started with an input to SAT, and that is going to be a lean formula with n variables and these are going to be as always xâ‚, xâ‚‚ and so on until you reach xn. And we are also going to specify the number of clauses and I'm just going to use the letter m here so we're going to say we have m clauses and I'm also going to give them names so I'm going to call them Câ‚, Câ‚‚ and so on until you reach Cm. We're now going to construct a graph that represents or encodes this Boolean Formula here and we are going to do this just as we have done before. So, this part here is going to represent Xâ‚. This part over here is going to represent Xâ‚‚ and so on and this one here Xn. Now, the question of course is how long these parts for each X need to be, and that depends on the number of clauses because we're going to attach clauses to the variables here. In order to make this safe, we should construct this part so that we have m of these edge crossings here because then we know that for each clause we have an edge where we can attach that clause to. Now, if we have m of these crossings here this means that we have m+1 of these groups of three vertices here so we have 3(m+1) vertices in this part here and then we have one more vertex here, one more vertex here so +2 if we extended like this, and this holds true for all of the other parts here as well. Now, for each clause but of course also going to add a vertex like so and again this vertex here is going to represent clause 1 this vertex here is going to represent clause 2 and so until we get to clause m. My first question for you is how many vertices are we using to represent the variables so to represent xâ‚, xâ‚‚ and so on until we get to xn and I would like you to enter this as four numbers and so it's going to be some number times n plus some number times m plus some number times mn plus possibly some constant. Please give me these four numbers here to correctly count the number of vertices that we have here to represent variables.
The correct answer here is that the total number of vertices to represent the variables is 3(n+1+2), so the number of vertices to represent one variable times n. We have 3(n+1)+2 and the whole thing times n, which is equal to 3mn+5n. We have 5n, 0m, 3mn, and a constant of 0 here again.
The answer here is very simple, we have one vertex for each clause. We have 1 m vertices for the clauses. All other coefficients of this answer here are 0. The only vertices that we haven't counted yet are A and B, so there's two additional vertices, and now we know the total number of vertices that we are using here in our graph that is
Now, let's assume that we had the clause vertices connected to these variable gadgets here. Of course, in the same way that I showed you before, so that the clause vertex can be visited like this--paying one extra edge instead of going here if the clause can be satisfied and we're traveling along this gadget in the right way, then otherwise it will cost us more than one edge. Now my question for you would be--so if the Boolean formula has a satisfying assignment, what is the length of the shortest path from A to B, and by shortest path, I again mean one that visits all vertices. I want to give you the answer as before something times n plus some number times n plus some number times mn plus some constant.
Now, the important thing to understand to be able to figure this out here is that if the Boolean formula has a satisfying assignment then a shortest path from A to B that visits all vertices can visit each of these vertices by basically paying just one extra edge. Instead of going this way, we have to go this way exactly once for each clause. The length of the shortest path from A to B that visits all vertices is the same as the shortest path from A to B that does not visit the clause vertices plus m because we have to pay one extra edge for each clause vertex that we visit here. It's something plus m and we know that there is a path between A and B that visits each vertex exactly once, and so, the path length from A to B is almost the same as the number of vertices, it's just one less, so you can see this here in the example. If I have two vertices then the shortest path would mean those vertices is one so one less If I go 1, 2, 3, 4, 5 vertices then the path has length four and so on. What we have here is 5n + 3 mn +1 and then we have to add m. Our total here is 5m + 3mn +1. And now, we are almost done. We have shown that if the Boolean formula has a satisfying assignment then the length of the shortest path from A to B that visits all vertices has length 5n + m + 3mn +1 Where n is the number of variables and m is the number of clauses. Now, we also have to show the other direction of course. If there is a shortest path between A and B of length 5n + m + 3mn +1 then each clause in the Boolean Formula can be satisfied. We have a satisfying assignment. Right now, we have shown that if the Boolean formula is satisfied then we have a path of this length and now, we need to show the other direction as well of course. If we have a path of this length then the Boolean formula has a satisfying assignment. Why do we need to show those two directions? That is because the requirement for reduction is that our new instance that we constructed here is a yes instance if and only if this Boolean formula up here has a satisfying assignment Right now, we have shown the if and now, we have to show the only if, but this is actually quite easy because if we know that there is a path between A and B of this length here then we already know that each vertex is visited exactly once because this is the bear minimum of a tour between A and B given this many vertices. Secondly, we know that the tour will correspond to a variable assignment It will correspond to an assignment of true and false to these vertices here because otherwise we would visit a city more than once. We've already shown that and finally, we have also shown that each clause can be satisfied because we can only visit a vertex down here like that with paying just one extra edge if the assignment up here corresponds to a satisfying assignment. And now, we are almost done in showing that shortest tour is NP complete. I don't know if you noticed, but there is one small detail missing Right now, we are only going from A to B and we are asking for the shortest path from A to B. We are not asking for shortest tour yet and that is actually quite easy to fix. We'll just remove this vertex B here and make this edge very, very, very, very long over here and then it's not the length of the shortest path from A to B anymore, but it's the length of the shortest tour. And of course, that length is only true if and only if the Boolean formula is satisfiable And we're done. We have reduced SAT to a shortest tour. We have shown that shortest tour is in NP. So, now, our final conclusion this problem here is NP-complete Of course, it's a bit ironic that showing that a problem such as shortest tour is NP complete can sometimes feel like solving an NP complete problem in itself. That's why I would now like to show you how to even further simplify that problem is NP complete.
So, is showing the NP completeness of a problem always so involved with playing around with strange constructions such as weird networks? Well, the answer is in a way yes. Showing NP completeness can often involve playing around a lot and some gory details in the proofs. So, even today, there are still scientific papers being published that basically just show the NP completeness of a certain problem or set of problems. So, it is not an easy task, but luckily, there is a whole arsenal of known NP complete problems out there which I'm now going to show you. If you go on Wikipedia, for example, there is a whole list of NP complete problems from graph theory, network design, sets and partitions, and so on and so on. So, for most practical problems that you will encounter either they have already been shown to be NP complete or although likely be very similar to one or more of these problems for which we already know that they are NP complete. In this case, similarity is a good thing because similarity means that a reduction will, in most cases, be either much easier than what we have just seen with shortest tour or, at least, if you then look at the NP completeness proofs for those problems, then I give you techniques and ideas for performing the reduction that you are looking for. The foundation for this library was laid by a computer scientist called Richard Karp who, in 1972, showed 21 different problems to be NP complete, and that was basically the starting point for this huge list of thousands of NP complete problems. Now, let's see if you already have an intuition which NP complete problems would be most useful to show the NP completeness of other problems. So, let's say you encounter a number of problems. One problem will deal with clustering or finding large groups of related objects or you would encounter a problem that deals with covering a set of object as efficiently as possible. So, you have to select a few objects that is some way observed or-- no, covering is a good term other objects in the set or you could encounter problem that in some way deals with optimizing pathways. So, getting from one point to another point but there are few constraints up here that you have to meet. Here, you are trying to find clustered groups of related objects. Finally, you could deal with a problem that is about diversification. So, large groups of independent objects don't have anything to do with each other. And finally, something else. Now, you already know the five NP complete problems. You know the shortest tour, you know vertex cover, you know SAT, independent set, and clique. Now, what I would like to know from you is if you encounter a problem that basically arises in one of these five situations here which of these problems here for which we know that they are NP complete would be your best bet for proving a problem that falls into one of these categories here is NP complete. So, basically using this as a basis for a reduction. So, these are numbered and you can enter your numbers for the ones that you think match best in these circles here.
Now, of course, this overview is super subjective and far from complete and also maybe not always correct but nevertheless. I think clustering or finding groups of related objects, usually it's a good idea to try to do a reduction from clique. Covering a set of objects--that is basically the problem that Alice was looking at for her Telecommunications Company. Vertex cover is usually a good idea and there are certain generalizations of vertex cover called hitting set that can also be a useful tool in proving that problems like these are NP complete. Optimizing pathways--well, yeah that is shortest tour and also here you should know that shortest tour has a very closely-related problem and that is the famous traveling salesman problem. They are not the same but they are very, very close. Traveling salesman is basically shortest tour, but you cannot visit a vertex more than once, so it's enforced here, and traveling salesman or the shortest tour problem here, it is always a good idea to try to use these problems for a reduction when you want to show that a problem that deals with optimizing pathways under constraints is NP complete. Now, diversification/independent objects--yeah. If you're a bit test savvy, you would already have guessed. This is, of course, independent set, and then, finally, something else. Well, you use our general tool and that is SAT.
We already have a pretty good tool set for NP completeness. We have SAT. We have vertex cover. We have independent set. We have clique. And we have shortest tour, and I guess also traveling salesman. In some way, it's amazing, isn't it? that all of those problems here are NP complete, which means in a way they are equally hard to solve, although they are all quite different. Now, I promise you a library of NP completeness. What I'm going to give you now is four additional NP complete problems that are often very very useful for showing NP completeness or also for recognizing NP completeness, because even before you do a formal proof, it's usually a good idea to say, "Oh, this problem just looks very close to SAT. We better be careful. This could NP complete." You don't always have to do the formal proof. It can also be a good indication of how hard a problem could be. Before additional problems, I would like to show you a problem called 3-SAT, a problem called k-coloring, a problem called packing, and a problem called common substring. So 3-SAT is basically SAT, but there's one restriction and that is that each clause has exactly three variables and that of course is a nice assumption to make in many proofs of NP completeness, because if you have exactly three variables in each clause, these proofs often become easier to read and much cleaner. As a side info, 2-SAT so where each clause has just two variables, a solvable in polynomial time. So one number here can make a difference, and the resulting 3-SAT formulas look like this. So you have three variables here in this clause then three variables here and of course with another index and so on. K-coloring asks if you can color a graph with k-colors so k is given as part of the input. And what is meant by coloring is that you give each vertex a color such as here. So we color this one red, this one red, this one green, and this one also green. The constraint is you cannot color two vertices with the same color if they are connected by an edge. So this here would not be allowed, and actually, the graph I've drawn here cannot be colored with just two colors so you need three colors to color this graph. This here for example would be one solution. It cannot be number two. And of course that's stated as a question. So is it possible to color the graph using k colors? For packing, you have given a number of containers and objects. And the containers have a capacity, and the objects have a value and a capacity requirement. So you have containers like these that come in different size and then you have objects. You have little objects. You big objects. You have very big objects. And they all have different values. So this might be not so valuable. This might be a little bit valuable, and this might be very valuable. So usually you cannot put all of these objects here into the containers. So the question is what is the maximum value that you can put into the containers? And of course, you could have the case that, for example, the bigger object is actually worth less than the smaller object so there are lots of different combinations here and will actually investigate this problem a little bit more in one of the next units. Now, common substring is actually a misleading name because some people use this in a wrong way I've seen this happened before. It actually should be called common subsequence. If somebody says common substring, better ask them if they don't mean common subsequence because common substring is actually not an NP complete problem, and common subsequence is the following problem. You're given two strings so string one and string two. Let's say lemonade and blender. And what's the difference between a substring and a subsequence? A substring is always lots of characters that are one after the other. For a subsequence, you can basically skip certain characters. So e, n, a, e is a subsequence of lemonade but not a substring. And actually, we will do this as a little brief quiz. What is the longest common subsequence of lemonade and blender?
And the answer here is 5 because you can take the L, e, n, d, e, which you also find here-- L, e, n, d, e--so here's the sequence. Here's actually a substring so that contains common subsequence of length 5 between those two strings.
Now just to familiarize yourself with these problems a little bit more, I would like to do the same thing that we have done here for these five problems. I will now give you a number of practical scenarios. What I would like you to tell me is which of these problems would probably be most useful for attempting an NP completeness proof? So again we will give these problems here numbers, one, two, three, and four, and I will give you six practical scenarios where you can then choose which problem to match to the scenarios, so you could have a scenario in Bioinformatics, but you would like to compare DNA sequences to each other. And what you are trying to find out is how much information they have in common. You could have a scenario where you want to schedule computer programs. What I mean by this is you have a bunch of computer programs. You know approximately how much time you took those programs is going to take. And you have a number of machines and of course you want to get as much work done as possible within let's say the next hour so you have to decide which program to run on which machine or you could have a question about let's say classrooms where you say, "How many classrooms do we actually need for the next semester to teach our courses?" So there will be certain courses that take place at a certain time or that cannot be scheduled together. A new question is how many different rooms would we actually need? Or you could have the scenario where two programmers have been working on the same programming code. And one of the programmers has made some changes and the other one has made some changes. And now you need to get these two codes back together again, and you do that by figuring out what they actually still have in common. Another problem could be that you have a number of vans or delivery trucks that you would like to fill and you want to find out how many vans you need to transport all of these packages here. They have different sizes. They have different priorities and so on. And finally, a scenario that is none of the above so something else. Please match the practical scenarios to the NP complete problem that is most likely to occur in that scenario, and I want you to do this by entering numbers here that correspond to these four problems. You'll have to use some of these problems here more than once.
And now, of course, the answer is a little bit subjective because, since all of these problems here are NP complete, you could basically try an NP completeness reduction from anyone of those, but we were looking for similarity; so, bioinformatics comparing DNA sequences? Yes, that is a lot like common subsequence especially if those sequences have certain insertions and deletions in them. Scheduling computer programs? That is most often a problem related to packing. You have a number of programs and the number of machines and you need to match programs to machines as best as you can that is almost the same as putting packages into containers so that they are optimally filled. Actually, scheduling is almost an individual class of NP complete problems. If you look at the Wikipedia page that we just looked at, you should find a couple of problems in the section scheduling. Are K classrooms enough? That can be stated as a coloring problem. If you have a number of courses, and for some reasons, these courses cannot be held in the same room, then determining a minimum number of rooms can be the same as determining a coloring in that network. For this course here, we are using the red classroom, and for this room here, we're using the blue classroom, and for example, if you wanted to use the blue classroom for this course as well, that doesn't work because we have a connection here. You have to use another one here and of course another one here. That doesn't work as well, so four classrooms. Merging the source code of two programs have been working on, that is a common subsequence problem because the program as will have modified certain parts, will have deleted certain parts, possibly inserted other parts, so we need to find out what the true programming code still have in common. Filling vans? Yeah, that was an easy one probably. That is a classical packing problem because you're actually using packets. Something else always calls for the universal weapon and that universal weapon in the case of NP completeness is 3-SAT. Now, you have a library of one, two, three, four, five, six, seven, eight, nine, ten NP complete problems which are a good basis for showing NP completeness. Whenever you come across a problem where you think that it might be NP complete.
You can use these problems to go through the three steps of proving NP completeness. Stating your problem as a decision problem and then show that it is in NP, and finally, use one of these problems here or some other problem that you know to be NP complete for a reduction. To find additional NP complete problems, you can either go to the list in Wikipedia that I showed you or you can see if your local university has a book on NP completeness. One of the most famous ones is this one here called by most simply the Garey & Johnson, but there are also other books that will give you a number of NP complete problems that you can use as a basis for a reduction.
Now, before the end of this unit, two words of caution. The first one is that the border between NP completeness and polynomial time can sometimes be very thin. I already mentioned to you that for example 3-SAT, so where you just have three variables in each clause is NP complete but 2-SAT where you just have two variables is solvable in polynomial time and there are many other cases like that but of course this is good news because if your problem turns out to be just as hard to solve as 2-SAT you actually have a polynomial time algorithm for it although it might initially have seemed a bit harder or sometimes even if your original problem possibly is as hard as 3-SAT maybe you can look at a slightly different problem that becomes polynomial time solvable. Because oftentimes there are many different ways to frame the practical problem that you're trying to solve so sometimes you're lucky there. The second thing is an actual word of caution. Because this border here can sometimes be so fragile. It's very important to be precised in your NP-completeness proof. Because sometimes making just a little mistake in an NP-completeness proof can invalidate this whole proof and of course we don't want that. Now, it's time once more to congratulate you. You now know what NP completeness means and how you control NP completeness. And actually not many people can do that. Very few people know precisely what NP completeness means and also they're not capable of showing NP completeness. In the next unit, we're going to take you even one step further. We're going to show you countermeasures against NP completeness. Because even most people that understand what NP completeness means and that can also show NP completeness actually tend to give up once they've shown their problem to be NP complete. But that's actually not necessary because there are many many techniques that she can use to attack even NP complete problems. What should you do when you want to solve the problem and show that is NP complete? Should you carefully check your proof? Should you have somebody else carefully check your proof? Should you give up? Should you maybe try to think about ways of modifying your problem so that it could not be NP-complete or should you try to use the techniques that you're about to learn in the next units of this course.
And of course, the only thing you shouldn't do is give up. Everything else--yes. Carefully check your proof. Have somebody else check your proof. Maybe the NP completeness isn't there, and if your proof is correct, think about modifying your problem--maybe it becomes easier on that case. And finally, look forward to the next units where we will discuss countermeasures against NP completeness.