Video 2-10: Complexity for Optimization Problems

0:03 In the last subsection, we'll look at definitions for optimization problems and how they connect properly to the theory we've established for decision problems now. So, what is an optimization problem formally? Um it's a a lovely seven-tuple.

0:21 First of all, we have some have some specific alphabet in which you specify the input to the problem. That's the instance that we care about. And let me make this concrete in the context of vertex cover. Um So, the the alphabets here often maybe just binary.

0:49 In a way, you know that everything can be encoded like this. If we were to write down our Turing machines explicitly, maybe it's more convenient to allow some specific symbols here on top of that. Uh more important is the um I wonder if this wanted to be U.

1:21 Okay, U is just the name for the entire thing. That's fine. Um Nothing wrong with the definition, but I think the names uh I wanted the other way around. So, we have some we have language that tells us what are valid encodings of inputs. So, I said maybe this is always just 01 the alphabet. So, you can always write down any arbitrary bit string. Um here this capital L could be uh all encodings of graphs.

1:58 Uh all encodings graphs and one number. For the example of vertex cover, let me make that green. Then we may want to further restrict among all those encodings, um which ones are valid for our current problem.

2:31 Um often times this is the same as L. Sometimes you want to restrict further and say this um this is a this is subset of the instances I care about, but it might not be easy to recognize them. Otherwise, you could simply say L uh is already um is already there and covering you. Uh I think I'm assuming that to test whether some 01 string is in L should be easy. You try to decode it as a graph, and if it fails, then you give up. Whereas this IL may be um tricky to decide if a certain instance is in this set. Uh for for standard vertex cover, it would be just the same. For a concrete example of what it could be is maybe it's some some of these weird graph parameters. Maybe uh I'm making this one up for vertex cover, but it could be that we want only graphs of uh of tree width less than or equal 100.

3:48 If you if you don't know what tree width means, that's not so important. Um we also didn't cover anything of this. It's just some property that some graphs have and others don't and you can't easily tell from a graph whether it has this property sometimes. Okay. Then um for every such uh input that we get we have some mapping of feasible solutions. So M is just a set or is a uh it's mapping instances to a set of feasible Uh but we also must be able to um to efficiently decide this. Okay, this is next slide. This is the general optimization problem without any uh without any assumptions on whether it's polynomial time or NP or whatever. So in in the general sense any instance has some set of feasible solutions. In the example of vertex cover, this would just be sets of vertices.

4:57 So this M of M of uh a graph would be encodings of sets of vertices. Then we have a function value that tells you for each um such a pair of an instance X is the graph and U would be our subset of vertices. Uh the value of this feasible solution tells you how costly it is. In the sense of vertex cover, value would just be the size of the set.

5:32 So uh I guess I should write write this like this. So the number of vertices that we pick. So note by feasible we already mean that it has to be a vertex cover. So um I should I guess I should add this here just for clarity.

5:56 M is already only the vertex covers. There's always one if you're throwing in all vertices. There may be smaller ones. Value lets you decide which ones you like better. And then every problem has an optimization goal, whether you want the value to be small or large. Vertex cover. You want this to be small. Okay? That's the notation in general. This doesn't say anything about computing things. So, um the next one uh will will restrict that further. Um if you have such a problem, then and an instance, you call a solution optimal if it has has the optimal value. This is the formal way of saying this. The value of this specific solution Y feasible for your input X has to be goal min or max of the value among all the feasible ones. I think formally you have to define this, but it's kind of the obvious thing. Okay?

6:58 Have We call an algorithm consistent if it doesn't do nonsense. So, it always spits out a feasible solution. If you try to evaluate algorithms for vertex cover, they should at least produce some vertex cover. Uh that's what I'm always telling students in in undergrad algorithms classes. In your exam, rather write down an algorithm that does the right thing and is slow, than write some heuristic that may or may not work and you never know, and it's only fast, but not correct. I think the order should always be first correct and then and then potentially good. And that's what we mean by consistent here. Um Okay. And if you want uh if you chase if you say just solve in this context, it means optimally solve. Like, it's consistent. It's always algorithm B always outputs a solution that is in the feasible set of solutions.

7:54 And the one that it outputs is optimal according to that definition. Then we say this this algorithm solves the problem. Okay. Uh one one somewhat natural not so natural example is this one. We've seen a bunch of examples as decision problems that are actually optimization problems. If we go back through this list, um most of them have this extra parameter as a threshold. And you could just drop that and ask for the best of the solutions. The smallest dominating set, not for Hamiltonian cycle, but I could ask for the largest clique and the largest independent set and the shortest tour and the smallest number of colors, the fewest sets or the least costly sets and so on and so forth. Right? Many many problems naturally have this flavor of an optimization problem. Uh here's one that maybe doesn't immediately have this flavor, but it you will see it'll hunt us at some later point in the approximation chapter.

8:58 You can also have a a Boolean formula and say I'm I'm happy if my variables don't fully satisfy this formula, but at least the maximum number of clauses that I can satisfy, they should satisfy. So, as a as another example, um formally skipping skipping the encoding parts, um instances are just any formula in some proper encoding. And the feasible solutions are any assignments of variables to zero or one. You can concisely write this as a string. And then the value of some formula under some assignment is the number of clauses that are satisfied. And we want many of them satisfied. Okay? Now you may ask whether that's ever useful to satisfy a formal not formula not fully but only most of the clauses. And the answer is kind of yes as an intermediate problem. Uh we'll come back to that.

10:06 Okay? Now for the for the interesting part, uh we want this is general optimization problem. All I've really said is uh some standard terminology and and uh letters for certain things. The interesting part is um tying this to the question of of polynomial time or probably not polynomial time. And that's that's these definitions. The class NPO of NP optimization problems is a set of these guys where I can efficiently decide uh okay, I need I need L I in in P by then. Then I'm not sure why we have L. Um we need a polynomial time decider to check if our instance is one that we care about. So uh for vertex cover again, this was checking that the input is a valid graph. And the number for the threshold.

11:06 Where is the optimization problem? Forget about the number. What am I doing here? L is just the graph. Then there should be um a polynomial that tells me that any feasible solution isn't too big. If I had problems where even writing down the solution takes more than polynomial time, then it's it's kind of asking for a bit too much. And I'm I'm just excluding this here. To be an NPO, there must be a polynomial so that the size of any feasible solution is polynomially bounded in the length of the encoding of that of that instance. And there must be a polynomial time algorithm where if I'm if I'm given uh a hypothetical feasible solution in an instance, I can decide whether it is a feasible solution. So, both of these things for a vertex cover problem are completely boring and trivial. The first one is uh sets of vertices are are not large.

12:20 are small. At most n. At most all vertices. And checking if it's a vertex cover And lastly, I I want to be able to compute the value of a solution in polynomial time. Again, for vertex cover, this is count the vertices in the solution.

13:06 So, this class plays the role of NP for optimizer for optimization problems. For the feasible problems, PO, the polynomial time solvable optimization problems, uh we require everything from the above, but also that there is a polynomial time algorithm that's given an instance of a problem and outputs an optimal solution.

13:34 As you would expect, uh the side remark is all of the other conditions are also assumed. For example, we can't have even if it's easy to find an optimal solution, we we don't allow that there are very long feasible solutions. These you have to somehow uh forbid.

13:58 Okay. Now, to make things a little more confusing, we have now different types of problems. Namely, we could either ask for an optimal solution or just for yes-no question. That's the um columns here. In the right column, we want to find an optimal solution. And in the left column, we only check if it's if something below or above a threshold, better than a threshold, exists. Now, there's also um the distinction between just outputting yes-no or um a single number. I guess that's why I wrote single value. Here it's a yes or here it's a no, and here it is um for the optimization problem, find me the uh the value of the optimal solution, but not the solution itself. And sometimes this is indeed a bit easier to do. Uh whereas in the in the second row, I want the actual feasible solution or certificate. So, let me go through this uh very briefly. The the decision problems is what we talked about all the time.

15:11 I'm just giving given an instance, ask a yes-no question. Do you like this input or not? The other end of the spectrum is what we just discussed, optimization problems. I give you an instance, and you give me an optimal solution that has the best possible value. It makes also sense to do the other two corners. Search problems are still asking just a yes/no question, but instead of saying, "Yes, there is a feasible assign There's a variable assignment making this formula true. I want you to give me one." Whereas if you say, "No." I say, "Okay. I trust you, buddy." Um for optimization problems on the other hand, you can ask, "Give me just the value of an optimal solution. I don't care about the solution." That's the evaluation problem. All of these exist um in principle. Now, there's some relations that are easy going from the um the bottom to the top. That's easy because you're just throwing information away.

16:18 All right. If you have an optimal solution, then you can evaluate it and just give me the value and forget the solution. If you have the certificate for a yes instance, you can just say yes and forget the certificate. Less clear is the way from top down.

16:37 So, these these two are the the trivial ones going going up. From a threshold to the optimal value, that's that's this one. Um if the set of values is somehow discrete and not too large, then we can just binary search. All right. This is from here to here.

17:10 by just asking for um several thresholds until I've nailed down where the optimal answer will be. But, it needs this assumption that the numbers aren't too big here, right? This is I mean polynomially many bits, the numbers would be uh super exponential. This is It's not a very strong requirement. But, in principle, it's there. Um from decision to search, so going going this way down, this is seems to be a more interesting question. If you name any of the problems that we've looked at, chances are rather good that you can do it in a problem-specific way. And you'll look at this in the tutorials. And when you see this on all the examples you try, you might start thinking, "Okay, this just has to work always." But, it seems it's a specific property um a certain property called self-reducibility that's uh it's not in general clear how to do it. And it may um I think this is a bit of an a conditional question. It It's certainly not known whether it's always possible.

18:20 Okay, also for um for NP-complete problems, specifically the you can always go from one to the other under the assumptions we've made. That's kind of the the rationale behind defining the optimizations problems the way we did is that that these four aren't uh really a problem.

18:49 I think this is uh apart from apart from this. This is um subject to the self-reducibility question. Okay. So, try to keep these separate in your thinking whenever someone asks you a computational question, you may want to sort it into these categories what what they what they're really asking you to do.

19:16 Okay. Um Formally, this is what we've done all the time. If you have an optimization problem, then let's uh introduce the notation, then threshold U is the decision problem where you fix a certain threshold. Now, formally, it's it's the set of all possible thresholds that are making this true. So, if you have a minimization problem, then your your threshold language consists of pairs, namely the instances of the optimization problem. Again, think of vertex cover, here's a graph. And K needs to be Well, K2 is just the uh the binary representation of the integer or the encoding. Um All the numbers here where there is some Okay, vertex cover of uh at most that size.

20:16 So, I can put all numbers larger than the the the optimal solution, and that's going to be the threshold language. And the convenience is that now we can ask um about NP-hardness of optimization problems by just looking at this language. It's intuitively what we've done all the time. For vertex cover, we also had with formally defined vertex cover as a decision problem where you already give the threshold. In hindsight, you can say what we defined as vertex cover was really the threshold version of the optimization version of vertex cover. Uh back and forth.

21:02 Um not hard to show or follows follows from this directly, I guess, from from the discussion. If you have an optimization problem in NPO and the threshold problem is NP-hard, then this optimization problem will not be in this polynomial-time solvable optimization problem class PO unless P and NP are the same.

21:27 Uh let me skip this. Um It just constructs uh the solver. And uh that's as one example, we can show that this max sat problem is is NP-hard as an optimization problem by well, doing a reduction, right? That's uh it's asking about NP-hardness. What we have to show is that the threshold problem of this max of this optimization problem is hard. So, we do a reduction from some known NP-hard problem to this threshold max sat problem.

22:03 And this is rather easy. If we're given some three sat instance with M clauses, we simply declare, "Ah, you have to solve all of the clauses." Ta-da. Then the only feasible solutions in this threshold problem are uh solutions that fully satisfy the formula. Okay.

22:35 So, this last part in in particular tries to give you a bit of a formal grounding if uh if you need it. I more and more feel it's often not needed. Uh the definitions make some corner cases rigorous, and that's that's their value. Um for the typical kind of proofs, the way we've done it before, that you say, "I'm I'm picking a a decision problem that models what the optimization problem really asks," is the threshold definition. And then showing NP-hardness for that is is the the usual case. But now we've put a bit more formal grounding behind all these terms, polytime and decision problems and languages, Turing machines for the model of computation. And looked at optimization problems.