cs313 »

cs313 unit 2.2

01 q Gathering Evidence

So since finding a mathematical proof for showing the intractability of the problems that Alice, Bob, and Carol are working on seems to be rather hard, we're first going to start with gathering evidence that their problems might be intractable. Of course, we don't yet really know if their problems really are intractable because as we have just seen there are also arguments why their problems could actually be tractable because just having an exponential number of solutions does not necessarily mean that their problems are difficult but we're going to see how it turns out. So how can we gather evidence that the problems of Alice, Bob, and Carol could be intractable? One way could be what we have done in the last unit and that is if you recall in the last unit we showed that all of these three problems are either tractable or intractable. So one way to gather evidence that they are intractable is to find more and more problems for which we also don't know polynomial time algorithms and connect them to the problems that we know. So if we had this huge network of problems but we say if we find a polynomial time algorithm for just one of them, all of them would be solvable in polynomial time but nobody has yet found such an algorithm that would already be rather strong evidence that also clique, vertex cover, and independent set might be hard. So we might, for example, end up with thousands of highly relevant problems for which no one has so far found a polynomial time algorithm and if they're all connected that would be not a mathematical proof but it would be a somewhat convincing body of evidence for these problems' hardness. And in fact, I will introduce you to such a collection of problems at the end of this unit and we'll also have a closer look in the next units. But today actually, we're going to do something that is a little bolder. We're still not going to be able to achieve a mathematical proof of intractability but we're going to do something that I would say is somewhere in between gathering evidence and a mathematic proof. And the way we're going to do this is as follows. I'm going to introduce to you a type of computer that is extremely powerful. So powerful in fact that no one has ever conceived if it could actually be built. And then what I'll show you is that if there was a polynomial time algorithm for vertex cover or clique or independent set, that would be like having a blueprint for this super powerful computer. We won't be able to show that it's imposible to build such a computer, but it is pretty good evidence that those three problems up here are very tough problems to solve. So what makes this computer that I'm about to introduce to you so powerful? Well, roughly speaking, it's so powerful because it has the capability to guess things for us and it will guess them correctly but you're going to see in a minute what I mean by that. First of all, let's have a look once more at the three problems: click, vertex cover, and independent set. And have a look at how a machine that would be capable of guessing things for us could potentially make the solution to these problems very easy. And we're going to do this as a quiz and what I would like you to think about is what the three problems we have been talking about so far have in common. And I'm going to give you a number of choices and I would like you to tell me which ones of these you think are true and there can be more than one. So there's four possible choices here and again more than one of these can be true. So what do all of these three problems up here have in common? Choice #1, we have not found a polynomial time algorithm for them yet. Choice #2, they are not practically relevant. Choice #3, the simple algorithms that we have found so far go through an exponential number of solutions. And finally, for the simple algorithms, for any given 0 and 1 assignment to the vertices so we have already assigned the values of 0 and 1 to them, it is relatively easy to figure out if that assignment is a valid solution. And if it is a valid solution, how large that solution is? So please check all of these that are correct.

01 s Gathering Evidence

So the first one is obviously correct. So far, we have not found a polynomial time algorithm for the three problems here. We've shown in the last unit that they are practically relevant or at least slightly simplified versions of highly relevant problems. All of the simple problems go through an exponential number of solutions. That's what made all of those simple algorithm so bad and their running time-- all led to the exponential running time, but the thing is going through that exponential number of 0-1 assignments is also what made those problems hard to solve. If you have given a certain assignment, checking if that is valid and how large it is-- for example, if it's better than a solution you have found so far--that is relatively easy. It's doable in polynomial time. Now, the answers to this quiz might seem rather obvious to you and you might be wondering what we're going to do with those answers, but I promise you it will all make sense very soon.

02 l if better

So in the last unit, we talked about the simple algorithms for our three problems that have to go through an exponential number of solutions to try all possible assignments of 0 and 1 to the vertices. And now I haven't told you yet what this super powerful computer down here in the left corner is actually capable of and the ability that this computer here has is that it can help us figure out the best possible 0 and 1 assignment to the vertices without actually going through them. And the way this computer can help us is that it has a special instruction that a normal computer or even the RAM model does not have and that instruction is called if-better. And I'm going to explain to you in a second what that means. So the if-better function basically works like a normal if-else instruction on the RAM. So the normal if-else instruction is if this part here which I haven't specified yet is true then this part of the code not yet written is executed and otherwise this part down here is executed. The second property is that calling the if-better function will cost us polynomial time. So a normal if-else on the RAM just costs one time step or constant time and calling this function here will cost polynomial time. And now here comes the special property of this function. Normally when you have an if, you would have to specify some condition here so that if the condition is satisfied this part of the code is executed. And if it's not satisfied, then this part here is executed. Now the if-better is a function that will figure out by itself if it's better for us, and I'm going to show you in a minute what I mean by that, if it's better for us to execute this part up here or this part down here. It will always, if you will, guess correctly which part of the code to execute. Now, the first time you hear this, it takes a bit getting used to. So let me give you one example for our vertex cover how we could use this powerful function to solve vertex cover almost trivially.

03 q Vertex Cover with if better

So we're working with the decision version of vertex cover here. So as an input, we're giving a graph G with n vertices and an integer k. And the output is "yes" if G has a vertex cover of size at most k and "no" otherwise. So the first time you see this kind of use of the if-better function it might still seem a bit strange to you so I'm going to explain to you what it does and how we're using it here. We're using this if-better function to guess for us which vertices to put into the vertex cover and which vertices we can leave out. Then we check if the assignment is valid although actually we wouldn't have to do that but I'll get into that in a minute and if the size of the assignment that we have found is at most k we say "yes, the graph has a vertex cover of size at most k and no otherwise." So as you can see, we're putting a lot of trust into this part here of the function because we're basically trusting the if-better to tell us correctly whether we should put a vertex into the vertex cover or whether we shouldn't do that. And that is why I basically said that the computer that has this function available is extremely powerful because if you can trust the if-better to do exactly what we want for us which is guess the best possible assignment then of course this significantly changes the running time of the algorithm here. So let's do a little quiz--what is the running time of this algorithm here for a graph with n vertices if we can trust the if-better function to perform as specified and guess the best possible assignment of 0s and 1s to the vertices.

03 s Vertex Cover with if better

And the solution here is if we have the if<u>better function available, then we can solve</u> vertex cover in polynomial time because as we said the if<u>better function works in polynomial time</u> and we're calling it once for each vertex in the graph. So we're calling it n times it works in polynomial time so this part here of finding the best possible assignment of theirs and once to the vertices that works in polynomial time. And as you know from before, checking if an assignment is valid and checking the size of an assignment that's also doable in polynomial time. So the total running time of the algorithm is polynomial in n the number of vertices, and the right thing is that, although you shouldn't probably anthropomorphise this, the if<u>better function always knows what will help us.</u> So if we were trying to solve clique or independent set instead of vertex cover, the if<u>better function would somehow know this and give us a different assignment</u> of 0s and 1s to the vertices, which would however still be guaranteed to be optimal, and that is what make this function so extremely powerful.

04 q Complexity Classes

So now with that kind of magic function if-better we could solve all the three problems we have looked at so far in polynomial time. We could solve vertex cover, we could solve independent set, and we could solve clique in polynomial time. Now theoretical computer scientists like to divide problems into so-called complexity classes. And a complexity class basically contains all problems that can be solved on a given machine within a specified time or a specified memory or even both. But we're going to stick with time for now. So if we draw this as a matrix and put time here and the machine here then so far we learned about two different types of time. We have learned about polynomial time and we have learned about exponential time, and we have the normal RAM, the model that has basically the same capabilities as any computer that you know, and we have just learned about the RAM that has the if-better function available. Each of these fields here in the matrix is a complexity class. So this field here, for example, would contain all problems that can be solved in exponential time on a normal RAM. So vertex cover, independent set, and clique would all be contained in this class. But of course they can also be contained in other classes and I would actually like you to figure this out as our next quiz and the question is, in which other complexity classes, so this one here, this one here, or this one here, can we put our three problems vertex cover, independent set, and clique? And I would like you to make a check mark if you're sure that we can put these problems into that complexity class. If you're sure that we cannot do that or if we're not certain, I want you to leave that field blank.

04 s Complexity Classes

And the answer here is as follows--so first of all, it's important to notice that a RAM that has the if-better function available is at least as powerful as a normal RAM because all we're adding is this additional instruction but we can still do anything that we could do before. So this here is clearly a check mark. Vertex cover, independent set, and clique would be solvable in exponential time. Also, if we have this if-better function available. And the second thing is that in the well sort of programming example that we just had we also saw that the if-better function is so powerful that it will allow us to solve vertex cover, independent set, and clique in polynomial time if we have the if-better function available. And of course this one down here, that unfortunately has to stay blank but not because we're sure that these problems, vertex cover, independent set, and clique don't have a polynomial time algorithm but simply because we don't really know yet. We will come back to this matrix picture here in a minute. But let's turn our attention back to the RAM machine for a moment now.

05 q Two Types of RAM

So, by now, we know two types of RAM machine. The first one here on the left is the one that we introduced in the first unit and it does not allow to use the if-better function. So, this is something that is although as we discussed it has some differences to your standard computer. It is more or less close to your normal computer. And here on the right side, we have the RAM with the if-better function and this of course is a much more powerful machine so as you can see it is buzzing with computational power here and this is totally unlike your standard computer because it has this guessing function about n and of course, if somebody asked us to build this sort of RAM machine at least I would turn them down immediately because it's not clear at all how we should write such a function. It seems far too powerful and at least to me frankly also a bit mysterious. So, that's also basically the difference between the two machines because here on the standard RAM, it's very clear what each of the functions that it has does. Actually, if you know what the machine is currently doing then you can always predict what it will do next because for every instruction it's very clear what it does given certain variables or inputs and not so with the RAM that uses if-better function above. Actually, most of the time unless this function is use, it's still clear what happens next but every time this function here is called, we don't really know what's going to happen next. It seems as if only this function here kind of knows. Or if you put it in another way, if you go through an algorithm that is written on a standard RAM then you can basically go through it step by step by step by hand and say how its going to behave. For this RAM over here, you could also go through it step, by step, by step but once you encounter this if-better function here, you could not really say what its going to do next. You would have to try different cases and so in order to better distinguish those two models, there is a special terminology in theoretical computer science called determinism and non-determinism. And this standard RAM machine because we always know what's going to happen next is called deterministic and surprise this one over here is called non-deterministic. Now, it's very important that you familiarize yourself with those two terms because we're going to use them a lot in this course, and just to make you think about them a little bit more, I would like to do a little quiz with you. So, what I would like you to think about is, if you're using the if-better function in a program and we run the same program code multiple times, can we get different solutions if we're running it on the same input or will we always get the same solution? So if you think that non-determinism can produce different solutions on the same input using the same code then please check yes, otherwise, check no.

05 s Two Types of RAM

And the answer here is no. So a non-deterministic RAM. If it's running the same cod on the same input, it will always return the same solution because this if better function here, although we don't know what it's going to do. It still behaves in a consistent way and this is actually quite important because non-determinism is not the same thing as randomness.

06 q Building a non deterministic RAM

As you have seen, non-determinism is pretty powerful, so the question is, of course, could we actually build a non-deterministic RAM? And as I told you before, I have no idea how you would do that, so if somebody ask me to build a non-deterministic RAM, I would turn them down although if you could build one of these, you would certainly become quite rich and famous. The next best thing we can do to building a non-deterministic RAM though is simulating one. And of course you will be asking yourself, well, if he doesn't know how to build a non-deterministic RAM, how is he going to simulate one? Well, the answer is actually not that difficult but I'll have to warn you because the simulation will not be very satisfying or at least will have to pay quite a steep price for the simulation. So the first thing we should probably talk about when we want to simulate a non-deterministic RAM on a deterministic RAM is how would we simulate a deterministic RAM on a deterministic RAM? So basically, a picture like this, you have a deterministic RAM and of course, it's branded as a deterministic RAM and on that machine, you do a simulation of another deterministic RAM and this might look a little bit more complicated than it actually is. So, all it means is that if you have a program code that you run on a deterministic RAM, instead of running this code directly, you have another program and this program is basically going through your code and simulating what your code is doing. And this program here which would be the simulator is basically looking at the code and simulating what this code would actually do. Without running it directly on the machine, so it's running indirectly on this machine here. Another way you can look at the simulation is this diagram here, so you start out with a certain program that you want to simulate and of course you also start out not only with the program but also with a memory of that RAM and if you remember in the last unit, we said that the RAM had actually different kinds of memory, some memory for the input, some for the output, and so on but we'll just draw this as a single memory here. So, we start out at the first line of code and then because it's a deterministic RAM, that line of code specifies exactly what's going to happen next, so it specifies certain modifications that we make to the memory, so we might change this variable here or even change two variables although this is not often going to happen in one single line of code, but we make some modifications to the memory and we're still in the first line of code here, then, we're going to check if that line here actually is a statement that tells us that we are done. If that is the case, then the simulation would also be done, but let's say that this is not the case. We can then go to the next line of code in our simulation and again that line will also specify some other things that we are to do, so most of the time it's going to be again changing variables, maybe it's reading the variable, but let's say it's also changing additional variables, so we check again if we're done, we go to the next line of code and so on, until we're done. And the reason why this simulation works and it actually works rather efficiently I would say, is a determinism means that each line of code specifies exactly what's going to happen next. Now for our next quiz, I would like you to think a little bit about the cost of this simulation or the properties of this simulation, so I would like you to tell me if instead of executing a program directly or running it directly on a machine, we do a simulation of that code. What are the properties of that simulation? In other words, what does it caused us to do such a simulation? Obviously, it will take longer because we are wrapping some other code around the original program, but how much longer does it take? Does it take longer by a polynomial time factor and by a polynomial time factor, I mean, if for example, the original algorithm would run in O(n²) time, or O(n?) time, something like that. Does it take longer exponentially, maybe, so if the original run in O(n²) time, we would now run and say (2^n) time or (2^n) times and square time, and finally, if this sort of simulation robust, so will it always give us the same result that the original program would have given us, or is there a possibility that such a simulation can make a mistake?

06 s Building a non deterministic RAM

And there are two correct answers here. The first one is the simulation takes longer by a polynomial time factor. Now, it's a bit difficult if you wanted to specify exactly how much longer a simulation like this takes. In my point of view, you would not even take polynomially longer but only a constant factor, but polynomial is safe enough because in this course we're mostly differentiating between polynomial and exponential running time. Now, the reason why it only takes polynomial time longer is that, as I said before, once we're in the certain line of code, this line of code specifies exactly what is going to happen next. So it's mostly an overhead of simulating what this line here of code does, but as we said when we specify the RAM model, each line here is a simple operations, so it takes constant amount of time on the RAM. I think it's fair to say that it will only take polynomially more time if you simulate what it does. It doesn't do anything really complex. So the second answer here is wrong. The simulation is also always correct because there's no involvement of randomness or guessing and such. So if the simulator is programmed correctly, we will always get the same result that we would have originally gotten. It only takes longer time.

07 q Simulating a non deterministic RAM

So, how can we now simulate a non-deterministic RAM on a RAM? Because that is what we originally set out to do and it turns out, it's actually not that difficult once we have our deterministic RAM simulator because what happens if you're in a given line or code? There's two different things that can happen, one it's a normal instruction such as one you would find on a deterministic RAM and in this case, the simulator can just go on running the same way that it would have gone for the deterministic RAM. The only difference is if the simulator encounters this, if better, here then it has a problem because then simulating what this line of code does is not straight forward anymore. The if better might execute the first part of the code or the second part of the code around which it has written, so we have to work a little bit on this part here of the simulation. So, we have to distinguish two cases. One is if we have a normal instruction, then we'll just do a simulation, but if we have an if better, then we don't know how the machine continues so what our simulator would then do, is it will branch into two different possibilities. So it will start two new simulations. In one simulation, it will continue assuming the if better function executes the first part of the code, so the one that came directly after the if better. And then the other case, it will continue assuming that the if better function executes the second part of the code, so the part that comes after the else statement. And of course, once you have this branching, you don't have one single simulation anymore, but you have to continue with two simulations. One simulation makes this assumption here, the other one makes this assumption down here. And if you now encounter the if better statement, then again, you will have to branch into two possibilities up here and the same thing down here. If you continue the simulation with the assumption what happened the first time you encountered the if better function, and now you go on, then again, if you find, if better, again you will have to split into two different possibilities. And of course, running a simulation this way where you have to split into two possibilities all the time comes at a price which I'm sure you can figure out by now. And my question to you is, if we have a program that uses the if better function, and times, how many simulations or how many different simulations do we end up running? Is it n simulations, is it n² simulations, is it 2^n simulations, or something else?

07 s Simulating a non deterministic RAM

And the answer here is that we end up with 2^n simulations, because each time that we encounter if-better we have to split into two possibilities and then the next time, we encounter if-better we have to split each one of those two possibilities into two possibilities each and so we end up with an exponential growth. And that is why I told you in the beginning that simulating a non-deterministic RAM on a deterministic RAM is possible, but it's a very unsatisfying simulation because we pay for it with exponential time and what that means is, for example, for vertex cover, yes, we can solve vertex cover on a non-deterministic RAM in polynomial time. But if we do the stimulation of that non-deterministic code, we end up with exponential time again. Now of course the question would be, could you simulate a non-deterministic RAM more efficiently? For example, only using a polynomial number of simulations. So, in a way we're back where we started. We found out that we can not simulate a non-deterministic RAM, but that's going to take us exponential time. So the question remains, is there a better way to simulate non-determinism ideally with polynomial time or does simulating non-determinism on a deterministic RAM always lead to exponential time?

08 q Polynomial Time

So remember the 2 by 2 matrix that we drew a while ago. We'll now have a closer look at this matrix as promised. So what we just found out by the way is that this part here anything you can do on a non-deterministic RAM in polynomial time can also be one on a deterministic RAM in exponential time. So any problem that is in this part down here would also be in this part up here. But since we are mainly interested in polynomial time, let's focus on the bottom part of this matrix for now. You'll come back to the full matrix in later units when we talked about exponential time complexity classes and remember that each of these squares contains all of the problems that can be solved in polynomial time. The left one on a deterministic RAM, and the right one on a non-deterministic RAM, and now, we'll give these names. So we'll call this complexity class here P, because those are all problems that are solvable in polynomial time on a deterministic RAM. And we'll call this here NP, because those are all problems solvable in polynomial time on a non-deterministic RAM. Of course, it wouldn't have been more consistent to call this one down here DP or something like that, but this is the way we named it. And now, what we also know is that any problem that can be solved in polynomial time on a deterministic RAM can also be solved in polynomial time on a non-deterministic RAM. We should probably rather redraw these black lines here like this because any problem that is contained in P is automatically also contained in NP but of course not vice versa. Otherwise, we would know that there is a polynomial time algorithm for vertex cover and the two other problems. So P contains all the problems that we know are easy. So, for example, finding the shortest path between two points in the graph or looking up an entry in the database multiplying two numbers and thousands of problems more. So basically, any algorithm you'll have come across in an introductory algorithm scores will fall into this category. And again, there are some theoretical nitty-gritty regarding optimization and decision problems here, but we can ignore that for the time being. So let's do a little quiz to summarize what you know by now. So given all you have learned, what can you say about P and NP? So I would like you to check which of these statements are true. The first statement is every problem in P is also contained in NP. The second statement is that every problem in NP is also contained in P. The third one is that P and NP are in fact equivalent. The fourth one is that it seems like NP should contain more problems than P or be larger than P, but we can't really say for sure. The fifth one is that vertex cover, independent set, and clique are contained in P. And the finally one is that those three problems are contained in NP. So please check every statement which given what we know by now you should consider to be true.

08 s Polynomial Time

I think there are three statements where we can certainly say by now that they are true. We know that every problem that is in P is also contained in NP. This is why we drew the picture like this. So, that's obvious. If every problem in NP is also contained in P that would mean that we have a polynomial time algorithm for vertex cover, independent set, and clique. We do not know that to be true yet. Of course, we also don't know it to be false, but it's not something we can make a statement about. And since we can't make a statement about this here, we can also not to say that P and NP are equivalent or basically the same. Now, the fourth one is probably the most subjective one so of course it seems like NP should contain more problems than P simply for the reason that non-determinism is just so powerful that we would not expect that every problem that can be solved in polynomial time using non-determinism can also be solved in polynomial time on a deterministic RAM if you just think about how much time our simulation took and of course it might not be the best possible simulation but I think it's highly unlikely. We can't be sure, but that's why I wrote here it seems like NP should contain more problems and not stated it as a fact so that I can make a check mark here. Now, finally, vertex cover, independent set, and clique, if we knew that they were in P we would have a polynomial time algorithm. Can't really make that statement right now. And finally, vertex cover, independent set, and clique, yes they are in NP. We show that they can be solved in polynomial time if we have the wonderful and magic if better function available.

09 q In P or NP

So, let's say we have a problem that we know to be an NP but we're not sure if it is contained in P or not. In that case, there is actually only two things that could be true so either that problem is actually NP but we missed it so we simply haven't looked hard enough to find a good algorithm for it or that's the other possibility the problem is only contained in NP. So, no matter how hard we look, we will never find a polynomial time algorithm for it. The cool thing is that for some problems we know that they are closely related enough so that it's actually sufficient to decide this question here if we missed a polynomial time algorithm or if we just have no chance. It's actually sufficient to decide this question for only one of the problems. So for vertex cover, independent set, and clique, in the last unit, we found out that those problems were closely related. So, let's just do a little quiz to see if you remember how these problems were related to each other. So, let's assume we found a polynomial time algorithm for vertex cover. In that case, we would know for sure that vertex cover is contained in P. So what will be the case for independent set and clique? Would we also know these problems to be in P or would it not be possible to make such a statement?

09 s In P or NP

And the answer here, of course, is that if we had a polynomial time algorithm for vertex cover, then as we saw in the last unit we would also have a polynomial time algorithm for independent set and we would have one for clique because as we found out solving vertex cover on a graph is basically the same problem as solving independent set. And if you have a good algorithm or a polynomial time algorithm for independent set, then through an easy transformation of the graph you can also solve clique.

10 l All in P or NP

So our three problems are so closely related that either all of them lie here in NP but not in P or all of them lie in P. We don't know which one it is but it can't be the case that, for example, we have just vertex cover in P and the other two problems here in NP. And how did we show that in the last unit? For clique and independent set, we showed that there was a polynomial time algorithm that could take a graph that was an input to independent set and transform that into a graph that we can use as an input for clique, and once we have solved the clique problem on the transformed graph, that same solution is also the best possible solution to independent set. So we have a polynomial time algorithm, so the algorithm transforms the input of one problem, say X, into an input of another problem, Y. So, for example, we take independent set and transform that graph into an input for clique and now you'll see one of the advantages of working with decision problems because the third condition is rather easy to state because we can now simply say that solving the problem Y on the transformed input yields the same answer as solving the original problem on the original input. So these three statements here are the same thing that you have seen in the last unit. So, we took an input which was a graph to independent set then transformed it into an input for clique and we found out that if we solve clique on that new input, then we would get the same answer that we would've gotten if we had solved independent set directly on the original input. And of course we also saw that the transformation works in the other way, so we could transform an input to clique into an input of independent set and now for a vertex cover and independent set, it was even easier because we didn't even have to transform the input, so basically the transformation was, we could keep the input as it is, the only thing is if we're working with the decision problem, of course, the answer will be a little bit different, so if we have a vertex cover of size k for a graph with N vertices, then for independent set, we must ask if we have an independent set of size n-k. But other than that, the transformation here is very easy.