Video 6-7: Lower bounds based on the Exponential Time Hypothesis (ETH) part 2

0:04 where we left off last time was using the sparification lema for three formulas to do anything interesting with it. And um the first kind of step here that that really shows you why this lema is so useful is that we can transfer this bound from the exponential time hypothesis to one that involves the size of the formula not just the number of variables. So a statement uh formally is unless this exponential time hypothesis is is wrong uh there is some constant so that every algorithm for this uh parameterized threes problem uh needs time exponential in n and k the length of the formula and the number of variables and so let's prove that um it'll be a proof proof by contradiction if you want. So we assume that such an algorithm exists but the point is we have to um get the quantifiers right. So there's an algorithm but it has a parameter C which is related to these constants and so the statement says there is a constant such that this holds. If we want to use uh a proof by contradiction we have to take the negation of that. So we have to say something about for all C. Assume that for all C algorithm that solves the satisfiability problem. This should be reset.

2:17 in the given time. So I well you state it as an upper bound. There's the exponential part as in here but we'll probably need some some polomial part that we don't actually care about. Um that can be generous but it it should only depend on the size of the formula not the number of variables. and it's a polomial I guess here n the size uh the number of clauses is equated with um the length of the formula uh because the formula is a threes formula that's um a constant factor difference. So that's our assumption. Now suppose um we're given some delta greater some there's some algorithm that depends on this delta uh that now solves the threes problem in the time that would contradict the exponential time hypothesis.

4:00 And so here we only have the exponential part or the number of variables. So if that was true, it would contradict the exponential time hypothesis because this is true for um for any arbitrary delta. So there can't be like the exponential time hypothesis uh claims um there can't be such a constant where this is no longer possible if I can find for any arbitrary small constant an algorithm that still does it in that time. That's the contradiction that we want to arrive at. And I guess it's um it's technically not a contradiction because we don't know whether ETH is true, but it would it would refute this exponential time hypothesis that people believe somewhat strongly is true. Okay. Um how do we uh construct this this algorithm B delta? One more parameter just because it's more convenient is is a delta half. Let's call that epsilon and that's what we use the spification lema with. So we take uh the spification lema invoke it with delta half. So the first thing is we get some constant k from the lema.

5:31 there's an epsilon for every epsilon that we give it, there's a constant K. And we could write that this is a function of epsilon, but it doesn't matter. It's time.

6:08 So that's the the constant there. Now the specification lema gives us what it tells us we can rewrite our given reset formula in this specific way as a disjunction with all the properties here. Maybe so that I don't have to go back all the time. Let me copy that part. So the first step that our algorithm B delta is it invokes the algorithm that's behind the spification lema, right? It's a constructive argument. You can construct from our given input the formula fi. We construct the equivalent formula big disjunction of S I from 1 to T using the code from the specification lema again and then we have these properties. So say with our epsilon delta half that's the first step maybe let's say step one now I want to decide my original formula. I know this one's equivalent. So I'm just going to try to satisfy this equivalent formula instead. Now this is a big disjunction. If any of the SI is satisfiable, the whole thing is satisfied.

8:27 So we call our um assum assumed algorithm I just have to tell you what this constant C is and I mean um again this is uh the way I'm presenting the proof is the final result of what you do normally you would just leave that and work out backwards what the constant should It turns out it works if you set it to delta over 2 * k + one capital k from the specification lema. And obviously if any of those is satisfiable then you return true. If all of them are unsatisfiable and return false and uh I mean this is what our algorithm AC uh tells you. It's a satisfiability algorithm.

9:39 So what we still have to do is analyze the running time of the overall algorithm uh B delta that we constructed here. The first step was calling the sparification lema. And there you have to peek at the in the small look in the small print. Uh the time is 2 to the epsilon k n to the c. I guess here the c is is an arbitrary polomial part. So um let me rename it to c prime because c for us has a specific meaning.

10:41 Okay, now we can plug in what we know for epsilon is delta part. That's the first step. The second step and by the way this is looking good because it's essentially the running time we try to achieve. So remember the goal is to show that we can solve P3 set in this time 2 to the delta K and a polomial here we have essentially that the key part is it only depends on K right not on the size of the formula. Now for uh step two, we have a lot of these calls, namely as many as we have. So t times as many as we have size. Uh I didn't copy it here, but the number of formulas is at most 2 to the epsilon k. Okay.

11:55 And the time um for each call on SI is the time for AC. And so that was by assumption this this lovely term. So two to the just doesn't fit 2 to the C * N + K and then a polomial factor. What's this? This bit.

12:22 Now we have to plug in what our C was uh which is is this. So we have the 2 to the epsilon K from the T. Then we have 2 to the this thing delta /ed K + one and then N + K. Um but I should say here N is a different N. This n is maybe we can call it n i or so. It's the it's the n i is the size of the formula pi. That's what we call this algorithm on. We don't call it on the original formula. We call it on each of these little uh clauses. Well, disjunctive clauses. I don't know the little formulas s I and that's the last bit where we need the specification lema again going back up one more time the number of classes is bounded by capital K * K K and if you plug that in uh so N I is less or equal big k. So here we have capital k + 1 * k. So that just cancels with the k + one here. So this this one cancels with the k + one and I have a factor k that I have to pull out.

14:17 And I could have plugged in what epsilon is here straight away. That's a bit nicer then. And you see we can simplify this to n to the delta k sorry 2 n to the b.

14:41 And if you add up the two steps, the second is actually dominating everything. But uh the overall time is of this form. You can be generous k and take the product of the polomials doesn't matter but this is um this is indeed this kind of time I guess I should not have the same say b here let's say b prime the point is it needs to be some polomial Okay, so we've we've constructed an algorithm B delta that somehow solves the problem in using I mean using uh our assumption it solves the three satisfiability problem in a time that contradicts the exponential time hypothesis. So if we believe in that hypothesis, we should refute our assumption. And that means we can't have an algorithm that even has uh this this subexponential running time because for every C in the size of the formula, it doesn't work for the variables. It doesn't work for the size of the formula. That's what the spification lema gives us. Okay.

16:16 Uh so this was um this was the key proof technique. Now we didn't maybe not care so much about threes itself. Uh we wanted to say something about vertex cover. Uh but virtually the same argument goes through if you take vertex cover and use what we've just shown in a way. So um you can you can take the same template um and maybe to make this explicit let's really copy things as much as time. Yeah in the time claimed in in the statement. So again the negation of needing exponential [Music] time would be something like uh times a polomial in in n. So you make that assumption from that we uh build an algorithm that solves a problem that seems to contradict and we can uh take the shortcut to the previous So this time we work towards uh using this one.

18:23 So again the template was suppose there's an arbitrary delta given or I guess yeah from that suppose we can construct an algorithm delta That solves uh Oh, come on. [Music] And this time we're only aiming for delta x n the size of the formula. And from the previous theorem we know this would already contradict the exponential time hypothesis. And so here this is actually much um a formula and we construct the vertex cover instance using the standard reduction from this picture. So I just take the normal uh I mean I don't know what normal means here uh but the most the most standard reduction from three set to vertex cover just works. can take it exactly as it's given threshold using this reduction. And just to make it visual, there's this uh triangle for each claw. Oh, come on. There's this triangle for each claws. And there's these magic green edges between between some of the literals that are negated. So you know what that means and this is doable in polomial time. And let me just use our assumed algorithm on um two I guess. So here uh the question is what is the parameter that pops out and here the parameter um is 2 * n. If I start with a formula of size n um n clauses then I have to pick I have to check for vertex covers of size 2 * n.

22:01 So this two comes from from this reduction and if you use other problems you have to adjust this choice of of this parameter C. Um but yeah here it's it's relatively simple. uh now clearly a solves this problem correctly and it does this in the assumed time. The first step is actually polomial time. Though the overall algorithm solves your threes problem in this time and if you plug in what k is then you get a threes algorithm in this time and that's well it means the eth is false and then you can make make of that whatever you want.

23:25 Strictly speaking here is just copying. Then I'm inserting what I what we know about C and about K. here. Okay. So that's uh is one technique how you can get to some statements that certain certain the existence of certain algorithms is unlikely. It seems in in this case specifically unlikely that you can substantially push further the uh um exponential time algorithms for vertex cover. You can maybe push the constant of the exponential growth a bit further um but not all the way down to some something subexponential in K. Uh you can show similar results for other problems. And here um I'm sparing you with the proof but uh because we discussed this problem at some in some detail maybe you're curious just to know the result for closest string. Uh we had a the essential growth of our algorithm was k to the k. This was the kind of depth u bounded search algorithm that naturally pops out of the problem. And my point is it's a very simple algorithm and the statement says up to maybe a a constant well it's still an exponential improvement but the k the key growth of um algorithm solving this problem seem to require this k to the k component. So in for this specific problem closest strings is unlikely that we can improve the simple algorithm that we've seen by much. So maybe it's not worth looking.

25:20 Okay, a quick wrap-up of of this unit. Um, we've seen LPS as a versatile tool last week and we've mostly um used it for a better kernel of our vertex cover problem. And then on the negative side we've seen these reductions from the exponential time hypothesis which really the proofs become very simple as soon as you have the spification lema. Uh with that key tool the rest is a a twist on standard reductions. And so I think it's useful to know about this because often times you have a problem where you can relatively easily argue relatively easily argue that a certain as growth for your FPT part is inevitable. Um but there's this um magic step in between the spification lema.

26:25 That also concludes the overall part on fixed parameter retractability. Um I had a slide for this but I think I copied I didn't copy the slide deck. All all the slide would have said is fix parameter tractability is great but it still often leaves us with an exponential time algorithm or worse. uh unless this parameter is really small uh it may not solve our problem. The main uses for fixed parameter tractability is is identify which problems are hard because of what. So there's uh it it gives a more fine grain picture. It's a kind of an adaptive analysis and maybe you're lucky and your problem is actually not hard in the sense that your your instances are hard just in the worst case over all in inputs of size n. Uh but if if you have um if the best algorithms you know about um still run too slowly, it doesn't really help us further. If the the problem with the type of inputs we have is still too slow, um we have to compromise further if we want to get things faster.