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

0:04 In the last section on this um fixed parameter tractable uh unit uh we'll look at some further ways to show lower bounds for problems. So, so in impossibility results and what we've seen so far with W1 hardness reductions where you could show a certain parameterized problem probably doesn't have any FPT algorithm but what about uh problems where um where we do have some FPT algorithm but we don't know whether we can further improve the functional dependence on K. So maybe um let me spell this out.

0:48 We had W1 hardness as the key to tool probably not in FPT. and we had various techniques for designing fixed parameter tractable algorithms where that is not the k and of course we'll we'll pick on our favorite problem vertex cover again and remember I had this on the slides previously. Uh vertex cover we know algorithms with some constant 1.3 to the power k the parameter uh the threshold of the size of the vertex cover times some polomial in n. Uh that was possible. Can we do better?

2:41 So whatever the constant was uh I guess here we can safely put an n squ and that's going to be enough. Can we improve this further? In particular, this part and maybe uh at first sight it seems okay. What what else could you do? Like uh if the function It's unlikely that we can show some uh polomial that would be amazing but uh then the problem would be in in P and we would have shown P equals NP. So unlikely is very unlikely. What else could it be? Um it seems sometimes that there's nothing between polomial and exponential but that is very very not true very untrue. There's a lot of things between polomial and and I mean there's things like 2 to the square root n which is not quite is is smaller than any constant to the n uh but is also not polomial or there's quasi polomial where you have two to the log to some power of n say 2 to the log to the 5n which is essentially same as n to the log 4 n. These are all running times that are um yes I should have set k here instead of n uh but as a function in n these are all super polomial subexponential and it's not clear if you can improve this to subexponential from what we've seen so far all we have are uh upper bounds on this and we have no lower bound for a vertex cover beyond probably not polomial Okay. And that's what we're looking at here. Now, to um to make statements about this, you have to make a slightly stronger assumption than our standard P not equals NP or W1 not equals FPT. And these are uh these are usually uh grounded on some uh complexity theoretic hypothesis. And one of those is the exponential time hypothesis. is often abbreviated as ETH.

5:36 It appeared in some slides before. Um and formally it says if that is true, it's a it's a hypothesis. Nobody knows, right? This is unclear, but many people believe in this one. It asserts that there is a constant epsilon. So that every algorithm for PT where it's parameterized by the number of variables, um I guess it says what K is. I wish I would have said P variables threes. Um so every algorithm for the threes problem requires some time 2 to the epsilon k. In other words, there is some some 1 + delta and delta is greater zero. And uh we don't know what that constant is but the hypothesis says there is one and it's not zero. So that any solution for the threes problem in the worst case asmtoically and so on needs an exponential time. Okay. So again nobody expects polomial here but there's a lot between polomial and exponential but the exponential time hypothesis says no no no there's for sat it has to be exponential at least and we know at most as well. Okay.

7:02 Now the hypothesis itself is a bit uh unwieldy because it only says there is such a constant. It doesn't tell us what the constant is. It's a bit hard to refute or make sense of uh depending where you look. You can reformulate it. That's what I uh already said. Um the same thing is to say there is some delta so that three set algorithms need at least 1 plus delta to the k. Again some exponential just reexpressing how it's written. Um, you could also say there's no way to have an algorithm with runtime 2 to the little O of K. So little O again was something that converges some some function that if you divide by K converges to zero and that's not possible and that is often the definition. So this two to the little O of K is usually what people uh describe uh when they say subexponential.

7:57 Okay, that's why the name is called the exponential time hypothesis because it assumes there's no subexponential algorithm for set. All righty. So far that's just the definition and um the only thing I can tell you is that a lot of people believe that this hypothesis is sensible and it seems any kind of algorithm for SAT has this property that it needs exponential time.

8:29 So let's assume that this hypothesis is true or let's make this an assumption so that when we get some some results it would contradict this so that we assume the converse. That's how usual uh lower bounds work. So it's it's analogous to P and NP. We prove something is NP hard. What does that mean? Well, it means unless P and NP are the same, there's no polomial time algorithm for that problem. And so we want to do the same thing with ETH instead of P= NP u uh P not equals NP. So we can use this to show that uh some problem X can be solved in some time that depends on some parameter of X. Um if that implies an algorithm that can solve the SAT problem in this time. So essentially uh contradicting what we've had for all possible epsilon then that would refute the exponential time hypothesis. That's again the the tricky bit. So this says there exists some constant but it doesn't tell us what it is. So to refute that statement we would have to show there is an algorithm for every possible epsilon that solves the s problem in this time. And in this case, so C for example could be a function of epsilon. It could the uh for any constant epsilon n to the 1 / epsilon would still be a polomial.

10:01 Um but it has to decrease the uh uh base of the exponential part arbitrarily much. Okay. If we can if we can do this then unless ETH is false we know that X doesn't allow such an algorithm. So we can try to uh kind of reduce problems to three set and uh get algorithms of that running time for a contradiction. Uh the thing is here this seems tricky because uh it needs a reduction where the number of variables in the resulting formula is small and um that's not always the case or at least in in many prominent examples it doesn't seem to work. Uh this is a reduction I've kind of very very quickly shown you at the very beginning where we talked about classical uh reductions. is also one that uh you'll you'll have seen maybe in some other places or in in Karp's paper. Uh it's reducing um resat to vertex cover and it's just shown on an example. Here's some reset formula and you can turn that into a graph where you take uh for every clause you make a triangle with the vertices containing the literals of the of the clause and the triangle are these blue edges and then the bit that encodes the logic are the green edges which are connecting every pair of literals that are negative negations of each other. So here I have x1 here I have not x1 that's why there's this green edge. Okay. And then the reduction says uh that um this formula is satisfiable if and only if there is a vertex cover for this graph that picks exactly two uh vertices from each triangle. And you can easily show that you uh you have to pick at least two vertices in each triangle otherwise the triangle edges aren't covered. And um if you uh if you need more then that means that some of the green edges were not coverable by just picking two edges.

12:20 So in a way the literal that is true is the vertex that remains uncovered by the vertex cover is not part of the vertex cover.

12:29 Um you don't need to dig through the details for for making sense of what follows. The thing is that here the parameter that we generate is uh is 2 n. We need a vertex cover that's linear in uh the size of the formula. Right? If the formula has n clauses initially then it'll have two n it'll have n triangles. So you uh you need to take two n ele vertices in your vertex cover.

13:08 So before we can um make make sense of that, uh can we say something about the number of variables here? The thing is it doesn't seem to matter even if the formula has uh very few variables. the reduction wouldn't give you anything different. The reduction would still look the same and ask for a vertex cover of the same size. Um, so it seems it seems tricky to make this um faster by uh if you if you were um the number of variables doesn't seem to influence the reduction really. It's kind of ignored.

14:10 Okay, maybe maybe I can explain this bit and we'll do uh the rest of the proofs next week. Um, so far this is uh what what the exponential time hypothesis directly gives us is not good enough to do reductions of the sort um that we can get lower bounds for the uh f of k part in ftt algorithms. there's a key structural insight and unfortunately the the proof of this is is relatively lengthy and a bit more intricate so um is only available in the original paper is not is not unreadable but it takes us too far so I'm just stating the result without the proof uh but I want to explain a bit um what it what it does uh and uh in a way it's rewriting a certain threes formula so that the number number of variables and the number of clauses are similar.

15:04 uh formally it says um for every parameter epsilon that you give me there's some constant that I tell you um so that I can take your threes formula fi with n clauses and k variables and I can give you an equivalent formula so it's logically the same logically equivalent which is um a big disjunction of many smaller threes formulas and um I'm using the same k variables in these formulas, but each of these formulas only has uh capital k* little k clauses. So the number of clauses is linear in the number of variables of the original formula.

15:49 Okay, now this sounds like a magic thing that the problem is that it uh the number of these formulas that you need is exponential. you can control how many you'll get and how long the whole thing takes by specifying this epsilon. So the smaller you make epsilon um the larger this k will be but then the time and the number of formulas is slightly smaller but you have to pick a a constant greater zero. So it'll be exponential either way you can just control how small you want it to be. So uh we do 2 to the epsilon k such uh formulas s and the overall computation I guess is essentially linear in the output. Okay. Uh because I put this here let me let me explain what uh what sunflowers means um is basically if you have a collection of sets. So say these are um literals of some uh threes formula and maybe uh there's a lot of a lot of clauses that include the same same literals um but have some other literal uh added on them.

17:19 maybe a nonsensical one too. So, uh the algorithm essentially tries to find these sunflowers, so sets of clauses that intersect all in some one or two literals. And then um it says you can satisfy all of those clauses by either satisfying their uh center or by satisfying all the petals. So you can either satisfy this or all of those four together. And that's where this disjunct disjunction of three set formulas comes from. You get one part for the inner bit. Either that is satisfied or the end of all the pedals of what's left and you need a clever recursive algorithm um to make sure that you get get rid of enough clauses that way. Uh that's the part that's non not so not very clean or it gets very technical. Now let's uh before we formally show this next time let's briefly see why this is useful. Uh the magic part here is that we take one threes formula and get potentially many threes formulas, but each of them is small in terms of the number of variables that we had before. And that ties nicely together to ETH. The exponential time hypothesis said nothing about the size of the formula, the number of clauses. It only considers the number of variables. But then it says it's exponential in the number of variables. With this sparification lema, we can take uh standard reductions like the the one relating vertx cover and three set.

19:07 um even if they're uh only generating something in terms of the size of the formula, number of clauses, we can still use reductions against the exponential time hypothesis because each of these size is sparse in this sense that the number of clauses and number of variables are the same up to constant factors.