Video 5-4: Tail-nondeterminism & W[1]

0:02 In the next section, we'll look at a a further restricted model of computation. And intuitively, the motivation for this is if you go back to how we use the nams in our examples, say the peclick uh algorithm, we guessed the random vertices. Um and in a way, uh we imagine we first guess and then we verify. Uh if you think about it um the verification was actually in the click problem very fast. It only depended on uh the parameter. Um and in that case uh we could have said that that actually only the last few steps need the non-determinism. In this in this problem this was a bit of an extreme example. Um if you think about the circuit satisfiability uh by contrast you have to pick the variables and then still evaluate the entire circuit. That's going to take more time. So uh you cannot easily um push that all the way to the end. And that that maybe gives some intuition for the distinction there. And so the the model that we'll look at does exactly that. Uh it has to do the non-determinism at the end of the computation.

1:17 So that's called tail non-determinism. Um as we discussed uh this this uh WP hard complete problem is is too hard. So we have to restrict the class a bit to to only keep the slightly simpler problems. So um an enramm as before kappa restricted enramm for a problem is tail non-deterministic. If these non-deterministic steps occur in the last uh zones or many steps depending only on the parameter that's the important part. So h again is an arbitrary function but it only depends on the input via kapa. Okay. So as as before nramm the number of non-deterministic steps is bounded but it has to be at the end of the computation. And it turns turns out this um is the final answer for our reductions. Um it gives rise to this uh complexity class W1. So these are all the parameterized decision problems LC kappa that are decided by such a tail non-deterministic kapa restricted n RAM. It's a bit of a mouthful. Uh and if you wonder what the one comes from, that's from an alternative characterization of the same complexity class where this is a parameter where other numbers can make sense as well. But the point is that this uh needs a lot of logic and uh terminology from from boolean circuits and so on that that in the end is not used for anything. So instead I'm I'm using the alternative characterization where only W1 really makes sense. That's the uh downside. But uh the definition is more natural. It's just the class that allows such algorithms non-determinism bounded by the parameter and only at the end of the computation.

3:20 Hardness and completeness. Just as before, a problem is W1 hard if every problem in W1 can be FPT reduced to it and completeness adds that it has to be in W1. Now, how can we get to a complete problem this time? And it turns out this is uh is maybe a more natural complete problem than the one before, which is also why we can do the full proof. So, um that's the problem. It's called the kstep halting problem. Now people with some uh theoretical computer science background will remember the halting problem for Turing machines. The infamous problem that is not at all computable. Namely deciding whether a Turing machine on a specific input terminates or runs into an infinite loop. Um that is not possible with any computing device we can think of. And the same is true uh by by reductions about all programming languages that are Turing complete and so on. Now here we're looking at the halting problem. So there should be some alarm bells in your head ringing. Um but we restrict the problem so much that it actually becomes uh solvable.

4:30 So the input is a Turing machine an ordinary one uh no no u fancy things but it is non-deterministic um and it has some some input that is also given and this parameter K and the question is now just does this during machine accept the input does it terminate but after at most k steps if it keeps running for more than k steps we're allowed to say no Okay. And that's of course what makes the problem decidable. Uh you can just simulate the machine for a certain number of steps and then there's two options. It finished or it didn't, right? Uh no infinite loops in the decision. And so that's what makes this problem solvable. So uh some subtleties about about this problem. Um I guess we would have to somehow specify how we encode a Turing machine as an input to a problem. Remember it has to be encoded as a language somehow. You can invent various ways to do that and basically they'll they'll be okay. Uh both the state space of this Turing machine and the tape alphabet and all components of this of this Turing machine uh are now part of the input of our of our algorithm. So from the perspective of an algorithm that tries to solve the kstep halting problem, it cannot assume that the Turing machine it's going to get is of finite size.

6:04 Once we have that machine and we start simulating it, it is finite. But we're given the machine itself as part of the input. Uh so that that means um because the alphabet could be that big or the number of states could be that big. We can have up to n different nondeterministic choices in each step when we simulate the machine. So what I just sketched taking that machine and simulating it for a while on a touring machine uh that's already somewhat expensive. It's it doesn't look like it's in ft for example. Uh you would need to uh spend n to the k + one steps at least because that's the number of possible nondeterministic paths you have to follow.

6:56 uh a slight slight remark um is we don't actually need an input here to be given. The problem doesn't change if you assume that there's no input and the machine just has the specific input we're talking about baked in. You could augment the machine so that the first part of its program produces that input because it's a fixed one, right? We given the input to the kstep halting problem is a fixed machine and a fixed input. So you might as well combine them. Uh that that's a convenient little uh simplification. Now the the key result that we want to prove is that this problem is indeed a a complete problem for our new class W1. And so yeah, I guess I should should stress that the number of steps is the parameter we're looking at. uh I think I mentioned but that's important. Okay.

7:59 Um let's spend a minute to prove this just because I think it's instructive uh to see how these things uh work together. Um there's two parts because we're claiming W1 complete. The first part is W1. This is in W1. Uh that's hopefully the easier part. Um so we have to show that the problem of computing these K steps can be done with uh such a an N RAM. So the input to the problem is a Turing machine M and input X and the parameter K or the step steps K. And uh we'll basically use an an RAM A that simulates that machine. That's relatively easy. We we basically follow just the instructions of the Turing machine. Now I said before um from the perspective of this NRAM Turing machine can be uh of unbounded size and it depends on the it's it's given as part of the input but that's not a problem because the NRAM also has uh the register contents also can depend on the input size. The bigger the input the larger numbers it can handle.

9:59 Um the we also have to show that this NRAM is is kapa restricted and tailbounded though for kapa restricted uh how many nondeterministic steps do we need to simulate such a touring machine? Well at most k because we're only simulating it for k steps.

10:36 And we have some leeway. It could be a function of K in case the simulation is not perfectly uh getting one one random step in the Turing machine simulated with a single step. U but certainly we're um we're not running the machine depending on the input size. Uh it's just running depending on the parameter and tail non-deterministic follows in the same way. We're running the machine for for K steps. We might have to do some pre-processing to get the simulation setup. that might depend on the Turing machine size but then the actual steps only depend on K how often we have to do it and copying the output is is constant time because it's a decision problem it's only yes no this is in a way uh same argument and these can come fast and copying the output is is fast as well. Okay, so here that's that's that's the trick that um the simulation itself is bounded only by the parameter. Uh that was the first bit.

12:17 hard and for that we need given some arbitrary problem in non-deterministic And uh we have to show that we can we can solve um can output the same as this machine a using our problem of simulating ksteps of some touring machine. How are we going to do that?

13:24 So [Music] um when you when you try to simulate A then A is given some input some uh word that could be in the language L.

14:00 y or the kstep halting problem. Uh kstep halting problem. Let me abbreviate So uh we have to we have to give a reduction now that takes um this input y.

15:09 So we want to show that L kappa is ft reducible to our kstep al halting problem. So the input to the reduction is y and what is fixed is is a that's outside of the reduction right because the problem is in w1 we know there is some non-deterministic ram that decides l the reduction that we map here. So given this is given this input y that we would feed to a if we were to uh run that program right away. So we take this y and now uh we run the machine a for its deterministic part [Music] deterministic part. And now here comes the magic. Uh the deterministic part can be polomial in n.

16:23 Um no it can be ft but we're doing an FPT reduction. That's fine. Um so that has FPT running time but it's deterministic. So uh there's no no choice. It's um it's good enough to run this once at the beginning and then we uh we take a a snapshot of the machine at this point. Uh and basically we encode that. Um well what is what is this what is the state at the of the machine at this point? It's the memory contents and maybe an internal state, a program counter. Right? So this are. So we can take that and write that down and construct uh now a touring machine that simulates the non-deterministic tail of a. Okay, so that's that's going to have some slowdown. But again here the Turing machine we can give it uh a number of states that's big enough to represent the the number of nondeterministic choices that A is doing because we're constructing that as part of the input.

18:15 So I should say it's a nondeterministic touring machine. And we know that this tail has h of kappa of y steps that's from the from the definition of kapa restricted there's some function h so we know for how many steps um we will have to run this uh this cheing machine that results from that uh if it finishes in that many number of steps then uh a would have accepted the input and we can copy the output otherwise uh we can stop and and reject the input. So the output of the reduction now is this Turing machine. The Turing machine and then the number of steps we have to simulate it. And so you can check that this is an FPT reduction. uh it runs in FPT time because we run a for FPT many steps. Um we construct something uh that's [Music] um I guess the machine A is not even part of the input. It's constant size.

20:21 Um and the number of steps is is uh the parameter of the new problem. The number of steps is a function of the parameter of the input. So it's parameter preserving.

20:40 Okay. And I guess the correctness is is almost obvious the way we constructed. Uh if that machine terminates with that many steps then A would have accepted input Y and and vice versa. So that part here is is relatively boring.

21:08 Maybe we should uh write down it's an FPT reduction is the reduction takes FPT here that's parameter preserving comes from correctness belongs here as the next component is essentially by construction.

22:22 Okay. Uh, not too much time left for nice reductions. Um, but let's let's zoom out a bit again. So, we have the class W1 to remind you. It's um the class where you have a tail non-deterministic coverricted enramm that decides the problem and we found there is a indeed somewhat natural complete problem for the class namely simulating now a standard touring machine a nondeterministic one for a given number of steps where the number of steps is the parameter. So what can we do from this? uh we don't usually care about this halting problem. We want to decide uh more combinatorial optimization problems. Um and to get to those um we need some intermediate problems to translate away from uh from the machines. And here weighted SAT can be can be shown to have a variant where um this this is indeed W1 complete. And so the uh variant here is again the parameter is the weight of the assignment that you have to put but now satisfiability is is a a specific for normal form for formulas and in particular here it's it's a two conjunctive normal form. So it's the same as as in threes but with two literals per clause which uh is a bit awkward um if you remember because um so three set was np hard um complete but two set isn't isn't p um but it turns out if you ask for the weighted satisfiability uh that is no longer such an easy problem and indeed the parameterized problem where you ask for can you satisfy a formula in two conjunctive normal form where the weight has to be exactly k that turns out to be a w1 complete problem. So which in particular means uh it's got to be np hard right. So um to to prove this we have to go uh so um I don't I don't think I've included the proof for this theorem.

25:07 Um I'll look into uh how hard that was. Uh maybe it led too far. Um it turns out that this problem still is a bit inconvenient to do reductions from and you can restrict it a little further. Uh where all the negate all the literals are negated. So all the inputs are of this form. you have some not x1 or not x2 and not x3 or not x2 and so on. So all the formulas look like this. It's two things but you take the negation for all of them. And it turns out that's also w1 complete. And uh from that we can do uh sensible reductions.

26:20 Okay. So I suppose again here going back to the weighted satisfiability uh needs more logic than than algorithms. Um and so let's uh let's not do that. Um but instead let's let's uh as one final point at least see one interesting problem that we've started a long time ago with and see that is W1 complete and that's the the independent set problem. So parameterized independent set in exactly the same way as uh we find it before the parameter the canonical parameterization is the number of elements in the set.

26:55 As always, the proof has the two parts of INW1 and then the hardness. Uh for INW1, same as for Pclick that we've argued before, steps of a of an NRAM subset of the vertices. And then we use k square time to check that there's no edges.

27:53 So that's kapa restricted because we only do k guessing steps and it's tail non-deterministic because everything that comes after the guessing is bounded by function of of of the parameter only.

28:31 Okay. So indeed the problem is in W1 because you can solve it with a cover restricted tail nondeterministic n RAM. Good. Interesting bit is the hardness and for that of course we borrow one of the problems that we know to be complete already. So we take the pwat 2 cnf minus problem. I know it's it's lovely uh to juggle with these names. We prove pw set 2 C NF minus can be reduced to our beloved independent set problem. So what do we have to do? we have to construct a reduction and we have to embed our uh 2 CNF minus formula into um somehow a graph. So we're given an instance of this problem which is some formula and let me write it like this.

30:05 Um there's uh some some variables uh sorry it's a some some pairs. Um let me let me maybe comment on this first because the the problem is so restricted. Uh the way a clause looks like is totally specified by two numbers namely the indices of the variables. Everything else is fixed. uh it always is negated and it's always exactly two literals. Um so the formula always looks like one big and over um some set of pairs and then each clause is x i negated or xj negated.

30:51 Okay. And uh from that uh of course that's one input and we're also given uh weight weight. And now we have to construct a graph from this as input to the independent set problem.

31:22 as vertices. We just take the uh essentially the the set is the set of all these um clauses if you want. So it's all the combinations where I J is in this set I when when I say you're given the formula you could essentially just write down this set of pairs right that fully specifies the formula and so uh we take take that formula and we make every clause an edge. If you want to satisfy this formula you have to make all clauses true. And a clause is true if one of the literals is true. And a literal is true because it's negated if the variable is false. Okay, so setting all the variables to false would make the whole formula true. Seems like an obvious pro problem. But uh weighted satisfiability says exactly k variables have to be set to k to true. In this case, it's important that this is an equal. And so, uh, the the the problem really asks for choosing the right set of variables.

32:49 And so, um, if I, uh, if I pick an independent set in this graph, um, I'm picking a set of variables where there's no clause that connects them, which means there's no clause where two variables occur that are both set to true simultaneously. I'm only picking a set of ver of variables, set of vertices in this graph where there's no clause that connects them. So all of them only appear in clauses where there's some other variable that I don't set to true. So the clause is still satisfied. Okay.

33:23 So, set of size K, I guess, yeah, I should have said the parameter stays the same. uh that's the correctness in one direction in the other direction if I has a satisfying assignment of weight Otherwise the formula would have a false clause. Okay. So the reduction is actually not super interesting. Um the tricky bit is how to get um to the right to the right weighted satisfiability problem. Uh okay.

35:39 Uh we'll look at a few other examples in in the tutorials. Um there's one more reduction um that I put on the slides uh which is talking about a slightly different problem which turns out to be a good intermediate problem. It's the partial vertex cover problem. Um as at least briefly introduce it. So uh as the name suggests it has to do with vertex cover but now uh we're given both um size for the number of vertices the the set of the vertices that supposed to cover edges um but I'm also giving um a threshold for how many edges they need to cover. Previously that that was all edges in the graph. In this problem you can say h it's fine if they only cover 10 edges. So um it's a generalization of vertex cover and remember vertex cover itself is FPT. So uh we wouldn't expect it to be a hard problem a W1 hard problem. Uh but you can show that uh this partial vertex cover problem is indeed W1 hard and we can do a reduction from independent set. Uh but I don't know if we have enough time to do that.

37:07 I could briefly sketch it um maybe just um by picture. So how would we do it? So we're given an input for the independent set problem. uh it's a graph and an parameter k how many vertices we want in the independent set. We uh keep the same graph. Uh we set t the number of edges we want to cover to be k times the number of vertices. Uh so sorry that's that's not we don't keep the graph that's uh that's the other reduction. Um so we have vertices and edges. The number of edges we want to cover is k times the number of vertices in the input graph. Uh but the new graph consists of the old graph and then uh for each vertex we add some vertices [Music] from number of from one to the number of vertices minus the degree of that vertex and the edges are the old edges and we have to connect these up. So basically create a star we connect V with its V wis same same values for I so how does that look like in some that's not what I beginning. Right. Uh let me just draw the example. So here's our input graph where we ask for an independent set. Say we want uh two uh vertices in our independent set. This and this. And that's the largest. And now we fill up in in this um in this graph there's four vertices.

39:58 uh every vertex that's the construction here gets a number of pendant vertices added in the reduction which is uh the number of vertices minus the degree. So this guy has just one at the moment. So we fill it up to have degree four. Uh this one has two so we fill it up with two. This has two and this has three. So it only gets one. Okay. The choice of our uh threshold for how many vertices we're supposed to um how many edges we're supposed to cover is chosen so that we have to cover with every vertex that we pick exactly a number of vertices in the original graph many edges. And you see that this is only possible if you pick what was an independent set in the original graph. If you pick the red vertices then all the vertices here the resulting graph is is regular. So G prime is size of V regular which means all the vertices have the same degree.

41:25 And then the best way to cover edges is if the edges are disjoint. If the there's no edge between any two red vertices, then every red vertex covers size of the vertex at many new edges and they don't overlap. And that's exactly uh the case when the selection was an independent set in the previous graph.