CS 627 – Advanced Algorithms (Winter 2026-27) · unit page · YouTube
2026-11-09, 22:38

Click any sentence to play from there.

The transcript was generated automatically by YouTube's speech recognition and is offered as is. It may contain errors, in particular in concerning technical terms, names and formulas.

0:02 What we'll see in the next chapter is that a further restriction of our kappa restricted n rams um bit less intuitive or less less natural maybe even than this uh indeed leads to finally the the true answer that's is able to separate vertex cover and click for that matter. Uh the notion of hardness or the the complexity class is called w1. um already is sign signaling that there's a hierarchy there that we'll not really discuss uh but there is one and it it ends with WP the most interesting one is between uh just going to this W1 level and again I'm not going to explain what the parameter really needs because that's a whole bunch of of logic what do we do so it's still too strong what we can do is restrict when the machine is allowed to use non-determinism. So far we've restricted how often and this idea of tail non-determinism says yeah you have to do this at the end.

1:10 Uh if you branch out too early then I have to simulate all of these long uh computations uh in all the branches and maybe that is the problem. So instead now you get to do whatever uh pre-processing you want. Um, I guess that's a bit of a lie. It's it's okay to be f of k poly.

1:40 Uh, still ft time. Um, but the non-determinism has non-determinism has to happen in the last h of kapa step h of k steps. So um of course you can sprinkle in some extra computation but only bounded by the parameter and all non-determinism only happens there. Okay, that's called tail non-deterministic. Hopefully obvious where the name comes from. So instead of having computations that branch out and then go on for a very long time, we now want to go to something that that goes on for a long time and then only at the end branches out a bit.

2:31 That's the idea. And W1 is the corresponding class. If a parameterized problem is decided by a tail non-deterministic kapa restricted n RAM and the names do get a bit long but of course we need both we need that the nondeterministic steps are not too many and that they happen at the end then that problem is in W1 okay hardness completeness the notion of reduction hasn't changed that's been okay from the start but we included too many too powerful problems. So if uh if I can simulate all problems in W1 by an FPT reduction, then I'm I'm W1 hard.

3:20 At this point, let me maybe try to uh clear clear up or connect a few pieces that we've looked at. Um first of all, there's a class XP that we haven't talked about in detail yet. These are the problems that one can solve in n to the power f of k time. So you should think of that as as poly time whenever k is constant. But it turns out this is a um not much of a restriction. This still allows a lot of problems. Um of course this like you continue this right. This is part of of uh the intersection is of course uh included in both of the parts. Um how are par NP and XP connected? That's a more interesting question.

4:23 PAR NP might be even more powerful. Is this maybe they're unrelated in general? Either way for the more interesting cases is further down the hierarchy. So XP is this um class where um any fixed K makes it polinomial is good enough and par NP had a similar flavor if you remember you allowed non-determinism all the way through uh which meant hardness here implies that there's a a bound a fixed K that makes the problem np So if if bounding K by a constant in XP that means XP is easier than par NP right okay I'm not going to write this down wrongly I can look it up properly but in par NP even If you bound K by a constant, the resulting problem is still NP hard. Precisely all of the complete problems there were like this. Whereas for XP, if you bound K by a constant, it is polomial.

5:36 So this is certainly not included. Um whether all of XP is in par not obvious to me. Um that notwithstanding um we can show FPT is not in XP using some time hierarchy arguments that we didn't get into. Uh for the other parts this is um a chain of inclusions. Um that inclusion is obvious because an FPT algorithm doesn't use non-determinism. It's a real algorithm, but it uses FPT time. A tail non-deterministic kapa restricted NRAM that doesn't do any non-deterministic guesses is an FPT algorithm by definition. So there's nothing happening. Of course, same here. If I restrict to the tail non-deterministic part, that only makes it stricter. So W1 is never bigger than WP. and a kappa restricted enramm is still a non-deterministic FPT algorithm. I'm only not using the non-determinism all that much. Okay, this um yeah, I think is still true. Um but uh yeah with with this one exception it's all open and we'll usually try to show that a problem is W1 hard which then means if this inclusion is indeed strict as people believe it is not an FPT so it doesn't have an FPT algorithm.

7:23 Um there used to be this this the next time this pops up here right last time said the exponential time hypothes hypothesis was refuted in a constructive way giving an a slightly subexponential time algorithm for three set which also via a clever argument not completely obviously implies a similar algorithm for vertex covered. So chasing to lower the basis of the exponential or an asmtotic result is a bit pointless. Now um of course the algorithm behind this are completely useless in practice. Um maybe that will change but for now it seems like this is a theory result only whereas the FPT algorithms for vertx cover from last chapter these are very practical for the small k where they work. These are fast no bad constants hidden. It used to be that um you could say if these two classes coincide then the exponential time hypothesis fails and that was additional support for that inclusion not to be strict. Now that additional support is gone. It doesn't imply anything about W1 and FPT. It just means there's one extra reason where people said this is why we think it's une it's not equal. That no longer stands there. Um but there's nothing else it it um implies. Okay, let's um that's the definition of W1.

8:55 Let's make our way towards a hard problem. We'll again need something like the mother of all W1 hard problems to do reductions from or W1 complete problems to do reductions from like satis for NP and like the weighted satisfiability for boolean circuits was for WP and uh for W1 this this mother of all W1 problems is again a little strange in the following sense. The class W1 is defined with these n RAMs. Okay, essentially a non-deterministic algorithm that's allowed to use the last G of K steps nondeterministically for guesses and before has to be a deterministic FPT FPT time algorithm.

9:47 Now the canonical problem for W1 completeness talks about Turing machines of all things. uh it's the problem with the long name of uh short Turing machine acceptance and short here means the computation of the Turing machine of course you know the general halting problem all of this is undecidable but if I give you a Turing machine nondeterministic in general or kind of it's uninteresting if it's just deterministic it's nondeterministic Turing machine M and an input and a time bound And you're supposed to tell me after k steps of nondeterministic computation does it accept the input. This of course is computable. You just simulate it. Now the just simulate means including the non-determinism. So you may need to branch out and um in principle that could be um exponential in K again. Okay.

10:57 Uh note here that um the machine and x and k all of this is part of the input. So um for each in instance that I give you here. So maybe um let me go one step back. Usually when we think of designing a non-deterministic Turing machine, we think of building one that say guesses a variable assignment. So it has a nondeterministic step where it says I can either go here or here. and that corresponds to the variable being true or false. So um that would mean we have something like a constant to the k search space.

11:54 If that was all there was, then it would be I mean the what does non-determinism in the Turing machine really look like? I have a transition from my current state and input symbol and blah blah blah to some successor states. And in principle this is bounded by the number of different states I have or the number of different states and tape symbols is um it's bounded by the transition uh function or relation and that is ultimately bounded by the touring machine components. So alphabet and state space right say size of the uh gamma size of the tape alphabet size of the state space I think that's mostly it maybe u the size of the operations right uh let's say times three for I can either stay where I I am or move the head left and right. There's don't I don't think there's too many more options. You can from a current state go into all of these different options, but that is it. So if the Turing machine is fixed up front, this is a constant.

13:08 Maybe it's a bit larger than two here, but it's some constant. A constant to the K would be an FPT algorithm. So it would be some C to the K algorithm that is FPT now the trouble here why this so Again, we're trying to find the mother of all non-FPT problems, right? Uh why this problem is not in FPT likely is that the machine is part of the input. So, um as the input grows, the machine grows, the state space of the machine, etc. all grows with n. And so, this non-determinism is also um growing more powerful. it is really guessing out of some range that grows say 0 to n not a constant range. That's that's the the crucial point here why this is likely not ft but something like n to the k.

14:36 So the trivial algorithm um could still simulate this machine by picking n as a kind of safe upper bound for the number of different non-deterministic steps the machine can take and then doing k time steps and maybe um one extra just to be on the safe side to check uh if it has accepted after that or not. Um, that of course is not an FPT running time.

15:12 Uh, note that this is convenient to state the problem where the machine has an input, but you could also hardcode the input into the machine and say you're you're baking it into the rules. The first few steps are just do what the machine would have done on this input or or write the input on the tape different options. Um all of this comes down to the same thing. You can uh by by uh blowing up the state space a bit you can encode the input as part of the machine. So you could also have this without input. Okay. Um as the last thing for today let's show that this problem is W1 complete. So that it is indeed the mother of all W1 complete problems in our sense and we can then try to do reductions from this from this problem to other problems. Okay. Uh again I'll I'll leave out some details here. I don't want this to be all about uh models of computation. We want to get back to the algorithm algorithmic problems uh very soon. Two steps we have to show for for completeness. First, why is the problem in W1 is almost the the trivial algorithm from the previous slide works.

16:23 So, we're given our touring machine M, its input and the number of time steps we are supposed to simulate. Now, how do we simulate it? Well, we have to construct this specific non-deterministic random access machine that is kapa restricted and tail non-deterministic. I guess I left out the kapa restricted. So, um let's smuggle that in.

16:51 What does that mean? I'm allowed to use k nondeterministic step or f of k nondeterministic steps but only at the end of the computation. Uh what I can do here is um precisely that simulation. The nondeterministic during machine is supposed to only run for k steps. So um I might have some overhead for simulating that but it's going to be some constant uh per step or the nondeterministic random access machine. I mean you can literally have the tape in its memory and an extra memory cell for the state and that is it. Then the the transition table is stored somewhere as well. So I can I can simulate these k steps and these are non-deterministic steps potentially but my non-deterministic RAM can also use non-determinism for these last f of k steps. Um I can even do it here with with f being linear. Okay is this this direction is easy with this powerful machine simulating the simple Turing machine. That's the easy part.

17:56 Now let's talk about the hardness. Given some arbitrary parameterized problem in W1, I now have to show that I can simulate with my uh Turing machine decision problem how this uh W1 problem uh works.

18:15 What I get from being in W1 is that there is a tail nondeterministic ka restricted nondeterministic random access machine A. I stopped reading that out. uh it's the thing here and uh it has some tail length that there exists some function h so that the last h of k steps are nondeterministic. Now if this thing is given some input y uh we can simulate what this during what this uh dur what this nam does or the deterministic part there's going to be some amount of time it spends deterministically before it branches in these last h of k steps that will reach some configuration of this non nondeterministic RAM. So it's it's some memory contents and some program counter. I guess that's all the configuration here here is register contents program counters and memory contents and then um the tail keeps running for h ofk steps in these hfk steps it can touch only a bounded number of memory cells it doesn't have time to mess up with more memory it may make guesses of r nondeterministic numbers but only that many and only for something that's bounded by the the deterministic prefix size. That's the definition of the NRAM or Capa restricted N RAM.

19:41 So all of this is rather um rather bounded. So we're going to turn uh we're going to hardcode that into a fixed Turing machine on which we can then do our short Turing acceptance.

19:59 So we build a Turing machine M that has this this fixed input again hardwired and it has the uh the the configuration that this NRAM gets to after its deterministic prefix hardwired.

20:14 Uh all of this somehow encoded in the humongous state space of this Turing machine. That's okay, right? We can build a Turing machine that is large. It has FPT size. We have FPT time to build this thing. that much time. Essentially the only thing we are are bounded is we can in this instance of the short during machine acceptance problem only simulated for a bounded number of steps for k steps or k prime. So um we'll hardcode all of this into this this humongous touring machine with lots of lots of states. uh but then the guessing steps that are still needed only touch a few things and only take um only do gfk guesses.

21:01 So these we can leave for the during machine to simulate nondeterministically. So, um that way we've built kind of is almost I think of it a bit like um like some of um some of the latte tools work. They um let this weird unbounded latte machine run and then after all the preamble is processed they say ah snapshot of your memory at this point give me all the macros that are defined and then I can run the machine from there onwards. I feel this is a bit like that. So you have a compiled preamble uh that's after this deterministic prefix and then there's the hopefully not nondeterministic in in the case of latte but you know uh you leave the non-determinism so the actual document in your case for latte and here the nondeterministic guessing steps that are part of the tail you leave that for the Turing machine to simulate nondeterministically and what we produce This is indeed an a machine that doesn't take any input. It has everything already baked in. But u we ask whether it can accept in these k prime steps.

22:19 Okay. And with that it it decides this general w1 problem. Not a very practical approach, but that's not what we're after. Is maybe also not not much worse than the cook le reduction to get a sad formula.

← Video 5-3: Bounded Nondeterminism - W[P]Video 5-4: p-IndependentSet is W[1]-complete →