Video 5-3: Bounded nondeterminism & W[P]

0:02 In the next section, we'll look at a new proposal for a complexity class against which we can try to prove hardness for parameterized problems in the hope that this is a bit more suitable to show that certain problems are hard for which um that isn't a trivial statement. uh where the P coloring graph coloring problem we had this this fact that it's par NP hard um because it also is hard if the parameter is fixed at three. So here we want to try to include problems where this uh alone is not uh the case. So a fixed parameter doesn't make the problem hard um but it overall doesn't seem to allow an FPT algorithm.

0:55 Uh for technical reasons, it seems working with Turing machines for defining this class is is not convenient or um causes more problems than it solves. And I mean in a way this was just what I what I said before seemed like a natural definition uh just replacing deterministic FPT time by non-deterministic FPT time. um but it is in a way a too uh powerful class. So hard problems um are too hard in our case and for technical reasons Turing machines seem not to work well. I think um there's no no great justification other than that. Uh so we'll look at some slightly different models uh of computation but also um fairly easy to work with. Um, one thing I wanted to say here is uh we will restrict our our study here.

2:09 We'll look at parameterized complexity classes um to the the key tools uh to prove that a problem is unlikely to is unlikely to allow an FPT algorithm. Uh if you want the structural complexities say uh study finer distinctions between problems, you could go further than we go. Uh on the other hand, I also didn't want to just use reductions. Uh um one alternative in complexity theory would be you just nominate your favorite hard problem, the one that seems uh convincingly hard to you and you show that the interesting problems, the other interesting problems you care code uh can be reduced to this problem. So that they are harder than a specific problem. So here for example uh we could just say that the the parameterized click problem seems hard. Let me use the proper font and then try to reduce problems to um just to that.

4:16 So so we could we could try to establish uh say Let's write it properly. So you show that some problem you care about uh is at least as hard as the pclick problem and then just stop there and say yeah it seems nobody knows how to solve pclick. So uh I'm I'm going to stop looking for fixed parameter tractable algorithms for a uh it seems unlikely that they exist. But this is a much weaker statement than what we are used to from classical complexity theory. Normally we also do just a single reduction like this. Uh but we pick a problem here that's nplete. And so after we've done that reduction we don't just know that some new problem A is harder than some specific problem that we picked maybe threes or whatever reduction partner you used. uh but because that problem was nplete you know it's this new problem A is harder than all the problems in NP harder in the sense of reduces can everything reduces to it and that's a much harder state a much stronger statement because it means uh your new algorithm doesn't have this algorithm this efficient your new problem doesn't have this efficient algorithm unless all of these others uh also have one And if we were just to do this, it's it would be a much weaker theory. We would only relate uh problems to individual other parameterized problems.

5:47 So that's the two extremes. Uh one would be go full on the complexity theory and study all the classes and their hierarchies. Uh which might be suitable for a specialized complexity theory class, but I I feel here um would lead too far. On the other hand, I didn't want to just say, "Ah, okay, let's pick a a magic problem like Pclick and just pro proclaim that this seems hard." So, I'll try to do some middle ground. Um, the implication of that is that some of the definitions are um not the original definitions of the classes we are studying, but rather their alternative characterizations that people have proved about those classes. um and they overall make a round picture, but they don't exactly correspond to uh the sources where it's taken from. It kind of combines different different results. It's just kind a little disclaimer I wanted to to put out there. So, if you read up on on some of these details or dig a bit deeper, uh you'll find that um I'm renaming a few things. Uh but the essence is the same. What we want is some hardness class. And let's name the beast. It's going to be W1, which is not WP that we'll see in this chapter. So there's one more one more step to go. So the the goal will be to prove W1 hardness. And I'm not saying completeness because for some problems that wouldn't be true. Uh we'll only show hardness. For some problems it's also completeness. For others you would have to go a little higher to W2 and so on. But that that that part is this first bit where I'm not so interested in if a problem doesn't have an FPT algorithm. How exactly it fails to have one I think is slightly less interesting than um the fact that it doesn't admit one.

7:46 We'll maybe see some some other techniques later. The board is really annoying. You just have told me that you can't read the last line. Okay, that's for the setup. So, if we're not looking at Turing machines, what else is there? Well, many things but actually we see an old friend again. Uh for some of you it's the the random access uh machine. So uh if you want we can uh we can say it's the word RAM. Now there's an important um additional letter here the N RAM which stands for non-deterministic right. So it's a it's a word RAM which just means um it's it's a machine that has uh a long array of memory cells. Each memory cell can hold W bits. And we're supposed uh to interpret this as a number, an integer. And we can do the usual arithmetic operations on integers. We can also do bitwise operations um like a bitwise and and all these things. So uh just to recap there, we've we've had it at the very beginning. So there's there's a large memory with just uh indices. And the important part is that these are really also numbers. So you can use uh indirect addressing. You can use the uh contents of one register to tell you what memory cell to read next. So you can do pointers, right? Uh so we have these this is essentially unbounded. It's as big as you want it to be. Um and you have a finite number of registers.

9:57 say 100. It doesn't matter exactly what the number is, but it's fixed and independent of the input size. And then um you have operations for loading pieces. So you can can read a memory cell and load it into a register. you can write back to some memory cell and you can give the address that you're writing to as the content of another register content. Um, and you can do arithmetic operations and you can do the usual uh comparisons and and conditional jumps. That's that's just a a reminder what the word ram model is. Now uh there's an additional operation that's the important bit from the n we can non-deterministically guess a number. So there's a new operation. It's a fictitious operation that real computers cannot do. But you can say this register nondeterministically should now contain a number between zero and some up some upper bound that you give by another register. And uh this is the machines that we're um allowing our algorithms to use. Now again remember this is like NPS like non non-deterministic Turing machines.

11:09 You're not supposed to build this machine. Uh this is a an overly powerful model that we're going to work against. Um then we'll say such a um an enramm decides a parameterized problem language and and parameter parameterization. Um in the usual way like um how do we define acceptance? Uh I guess we have some output register and that contains a zero or one. Um and uh we call such an uh an enramm kapa restricted uh if its running time is FPT for the input. This part is the same as for touring machines. Uh also the space um I mean here okay me memory cells I would really want to say the space usage is kind of um following from the time you can you don't even have time to touch more than this uh but it's maybe less obvious than in the Turing machine. Uh we also put a bound on the numbers in the memory cells. So um in a way you could control this via w but uh it's more convenient to directly just say uh the numbers that we have are bounded in terms of uh the parameter. So in a way uh the traditional is just log n with a parameterized problem. We would say w can be um a power poly log n and oh sorry it's log of a polomial that's just log n and um some arbitrary function of k if you take a take the log here it doesn't really make a difference okay so these relatively natural things. That's just what an FPT algorithm means on a word RAM as opposed to a Turing machine. Uh but then there's this this second requirement which is important. Kappa restricted the number of non-deterministic guessing steps.

13:35 These new operations uh the fictitious magical operations, they're bounded in terms of the parameter. You cannot do uh arbitrarily many of those steps. Okay.

13:49 So how does this compare to um uh Turing machines uh and FPT running time? Um especially if you compare it to par NP there. We didn't have step two. We said nondeterministic Turing machine with a certain running time but it was allowed to do a nondeterministic step each time it does a step and so this restriction two here is is the key difference. Now you could have tried to do the same in a Turing machine restrict how often it does a non-deterministic step. Uh the problem there that makes this inconvenient is that in a Turing machine the nondeterministic guesses are actually finite. they're bounded for a given machine. There's a given number of states and the everything's finite and fixed. The alphabet symbol, the number of states and all that. It cannot depend on the input size and certainly also not on the parameter. Uh so these non-deterministic steps would only choose among a constant number of different alternatives fixed and constant. Uh and that turns out to be just an annoying model. You would have to somehow then translate that to allow a certain number of steps which uh should somehow be able to depend polomial on the input size and arbitrarily on the parameter. It it gets very messy and here is easier because you say the non-deterministic step is a little more powerful. It's allowed to guess a number um uh that that is unbounded in general.

15:37 um you can restrict it harder harsher on how many of those you do. So what I'm saying is the details of how the model works for this lecture are not so important. The key step is the non-deterministic guessing step here is more powerful.

16:10 Okay, then we can define um a new class of uh of problems which is called WP and um the naming will become a bit more clear in a moment. uh it's the class of all parameterized problems LC kappa that can be decided by such a non-deterministic RAM uh exactly as we defined it kapa restricted which means uh FPT running time FPT size of the registers and at most a function of the parameter many non-deterministic guessing steps Okay. Um that's a class of problems. So you can think about uh what kind of problems are in this in this class. Um so how about um say our our clique problem.

17:23 The point is uh let's try to be to implement the brute force algorithm on such a machine. So of course we need to use the non-determinism.

17:47 And what do we guess in the click problem? Well, K K. How many nondeterministic steps do we need for that? Exactly K because [Music] one. Okay, so we're we're using the nondeterministic step to tell us which vertices to pick and then we're just verifying that it's a click or check.

18:56 uh and that that actually takes only time bounded in terms of the parameters. So the whole problem hardly depends on the input size. Now on this n RAM uh only this this upper bound for the guessing step really needs the input size and so well I guess we can uh depending how the graph is represented maybe we have to walk through the graph to count the vertices and so uh the running time would be linear in n say let's let's be generous and say n plus um only really needed to count the vertices and then we have um k non-deterministic steps and then we have k squared to verify all the edges are present. Now this is assuming we have an adjacy matrix given but in this initial time you could also take any other representation of the graph and transform it into an adjacy matrix I guess in n squ time uh let's let's not get fuzzy about the details let's just put n squ here or number of n number of vertices the details here don't matter really my point is I just wanted to show you an example of how programs in this WP class look like because I think it's fairly natural. Um, apart from this guessing step, everything else could easily be implemented and uh the the plain brute force algorithm works. It's just that this this guessing step now allows us to use the non-determinism in actually a more convenient way than on a Turing machine.

20:47 So in a way uh it's a more powerful model. It's more convenient to program. uh it is a bit harder to use in proofs. Okay, certainly this is an FPT time and the whole thing is is kappa restricted because we only use k guessing steps. So uh that shows I guess I posted as a question. So the answer is yes. And most of the problems we had can really be cast in this way. In particular, all the problems where we had as part of the guessing pick a subset of certain things where the subset size is bounded by the parameter, right? All all these graph problems of the flavor of click and independent set and yes also vertex cover less interesting um dominating set. What else do we have? Uh all all of them have this this property that we're we're just guessing a subset of vertices and we can do that in that same way. Okay, so that sounds like a reasonable class.

22:01 uh to work with WP hardness we would need a complete problem or at least a problem that's uh that all of that class can be reduced to the definition of hardness and completeness is exactly the same as always. So a problem is WP hard if every problem in WP can be FPT reduced to it and completeness adds the requirement that the problem itself is in W of WP. Um now what could such a complete problem look look like? It would somehow uh have to work. So all all we get if we say we have an arbitrary problem in WP is there is such a kapa restricted n RAM and from that we somehow have to uh get a get a reduction. So uh the satisfiability problem popped out as as the right answer for classical Turing machines because we can simulate in a in a satisfy in a in a boolean formula how a Turing machine computes.

23:09 So we somehow uh need to do something similar here but we also need a parameter right it needs to be a parameterized problem and if we take SAT and look at the number of variables we know that that's in FPT right uh so that's not going to work okay I answered my own question but yeah I guess uh you would have remembered for sure uh so that that cannot work maybe as some other variant of SAT uh is more more promising. The key feature we have is we can guess uh numbers subsets. That's what um we've seen in the click example. But that doesn't seem to work too well with SAT or what what would that mean in SAT to guess a subset? Well, we can guess a subset of the variables. And so a somewhat natural restriction would be that we guess which variables are true, but we bound the number of variables that we allowed to set to true. And that's that's the weighted satisfiability problem. Okay, I think um I initially mentioned this when we started talking about fixed parameter algorithms as one option for satisfiability and at the time I didn't u didn't try to make it sound like a natural thing. But here if you if you come from this n RAM definition maybe it's not so uh not so unnatural that this might work. So the the problem is defined as follows. You're given a boolean formula as for satisfiability in general and also some some threshold K which is our parameter. And the question now is can you satisfy the formula with an assignment that okay let's be strict that sets exactly K variables to true.

25:11 Okay. And we call that the weight of the assignment. Uh that's just the the name that gets stuck. I don't know the number of variables that are set to true. So let's um let's show that this is indeed uh um in WP first.

25:45 So what would we do uh to solve that problem? Well, same algorithm as as for peak click. Because you're restricted to a weight k assignment, you can guess the subset of variables that you set to true and then you evaluate the formula under that assignment and see if it is indeed true.

26:21 Easy. Uh what you can also prove is that a certain variant of this problem is WP complete. Now uh in in this case I'll only sketch a bit the proof because um WP won't be the final answer for us anyways. It turns out you you cannot really make this uh work. So what we have to do [Music] problem. Um, and if you if you try that with ordinary satisfiability, so the boolean formulas as we know them, uh, this seems not to work. uh just because you you don't easily get a bound on the weight of the satisfying assignments. Uh but it turns out um that there's a slightly more powerful model of uh satisfiability where this this does work although the details will lead us too far. Um I just want to sketch briefly what this talks about and uh for that we need to talk about boolean circuits.

28:00 Um I don't know if people have seen this maybe u in the more technical part parts of computer science you're more used to working with these um the theory version would be you have variables as uh starting points and these will have some boolean value true or And then with a formula we we would normally um use uh well we would we would write the variable many times. here instead uh we can have and and or gadgets and they can just use variables as inputs. I'm I'm making up this formula now. It probably means nothing interesting. Uh just to make the point and here you could take this and this and So the the edges have a direction. They go from left to right in this in this picture. Um but the key point is I can use some part of the formula many times. Uh in a circuit the output let me add the directions explicitly.

29:52 So the point is um what's the difference between circuits and formulas? Circuits can be much more compact because uh if you spell out what I've written here as a formula um okay I would have to say what the output is I guess uh that's still missing. So this is a single thing that goes in here and that's not used. That's a bit pointless. Okay, probably this formula is completely uh nonsensical. The point is um you have an input variables as you have for for a formula and you have a single output but within the formula you can have sub expressions for example this uh this sub expression x1 and x2. Oh, and I haven't used any knots, right? That's not good. Let's include a a knot. This just has a single input and output. Um, so there's this part of the formula x1 and x2 and that's used twice. In a formula, I would have to copy it and write it twice. Whereas in the circuit, I can reuse the output of this uh of this single uh the single gate several times.

31:10 And that means you can have large parts that are reused and then the larger reusing parts are reused again. So in general circuits can be exponentially more compact than a formula. If you had to spell this out as a formula, it might grow exponentially. Which also uh then on the flip side means uh working with circuits as an input is often much harder because they can specify more complicated functions with less uh encoding size. Um and so you have less to work with because the encoding size is your input size from which the runtime is determined.

31:55 Okay, so that that's a formula. Um, you can always interpret uh sorry that's circuits. You can always interpret a formula as a circuit by just writing it as a tree. So maybe that's worth stating, right?

32:17 Uh but there's many more tricks you can do on on circuits. And the the key that we're using here is um that you can uh modify them so that they're satisfiable with a fixed weight. So the idea of the reduction We're given an arbitrary problem. We have to show um an arbitrary language L kappa in WP.

33:04 The claim is that this reduces to this um this problem. So the circ just stands for circuit just in case it's not circle cycle or anything like that. Um the idea of the reduction is from this we get there's an n RAM for solving this. Then we simulate um this NRAM uh uh with a multitape touring machine to get closer to formula.

34:44 circuit. That's a similar reduction as a similar construction as for the the proof of the cook lemon theorem. Uh and then comes the the trick on circuits which um makes the whole point about circuits necessary.

35:18 Um we can find the circuit D so that um C is satisfiable if and only if uh D is satisfiable with weight K. So several of these steps are not so clear, right? Uh I didn't tell you really what multitape Turing machines are and how we can simulate the word RAM operations. And um I also didn't tell you what this trick is. That would lead too far. So it's it's kind of just um a brief uh outline roughly what this looks like.

36:11 Um let's claim that's a a bit of a proof but that's that's roughly what it would go like. Um so it has similarity to classical complexity in some sense but you have to uh um do a few further steps to get the weighted satisfiability. The point why I think it's not worth sticking through the details here is that this is not the final Um, yeah, I don't think I have a nice example here. the the problem with WP is that it still seems too powerful. the key problems um that we were looking at say P class but it seems that we cannot actually reduce this problem P set circuits to uh P click uh in a way the circuits are too powerful and this this um WP complete problem is is too powerful to be simulated with something like peclick. Uh if you if you were wondering how to do that, I guess it's yeah subject to uh some some complexity theory assumption it isn't possible.

38:11 Waited out of circuits. Did I put that in normal parenthesis? Okay. So, the not here is important. I don't know. Uh, that doesn't seem to work. So, we found a class with a natural um complete problem, but it seems it's too uh too hard a problem.