Video 5-3: Bounded Nondeterminism - W[P]
CS 627 – Advanced Algorithms (Winter 2026-27) · unit page
· YouTube
2026-11-09, 26:56
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:03 In the next section, we'll see how to address the first flaw of this PAR NP completeness which just allows two powerful algorithms. Um, that's the idea of bounded non-determinism. Um, as I just said, PAR NP allows you to spend FPT time and every single step can be non-deterministic.
0:23 And so we'll try to um reduce that a little bit and edge our way closer to something closer to the problems or fine grained enough to capture a pe click. That's that's the the signature goal. H it turns out for one thing it's a bit inconvenient to do this on touring machines. uh I think it's not inevitable but it's a bit more natural to start with for this class um to formulate it in terms of a different machine closer to our word RAM and the the definition for this is called the nondeterministic RAM.
1:03 I'll comment on the differences to the word RAM in a minute. Um this this is two definitions in one. The non-deterministic RAM is just the random access machine with non-determinism. But then we also want kapa restricted. Okay. And n RAM is a unit cost random access machine. That's the difference to word RAM. In word RAM we assume we have a fixed word size.
1:36 I think word round didn't really play any role in this module and that's fine. Uh from from other modules the the real algorithms when you care about the running times in a sense that is closer to actual machines and what you can implement then the word RAM is the natural model to pick. H in the word RAM you have memory cells of W bit numbers and on W bits you can do arithmetic operations in constant time. If you have bigger numbers, you need to simulate that with W bit memory cells. And um unit cost here means no, you can have as many bits in your memory cells as you wish and they shall cost you constant time to add or multiply or whatsoever. So this is a rather um it's a bit unrealistic. It's too powerful a model. But we're doing complexity theory. So if a powerful model cannot simulate your algorithms, this is a stronger statement in a way.
2:36 Okay. Um, unit cost RAM is that thing. So, think of a RAM just for completeness is you have a an unbounded memory divided up in cells that can hold a number each. You can think of this as being uh infinite to the right and then you have a a CPU that can access these by index. So the big difference to Turing machines is that you can directly say I want memory memory uh cell 17,000 and you just jump there in constant time. That's what the random axis really means. Right? That's is that's the difference to a Turing machine.
3:18 Okay. Uh then we additionally have one single non-deterministic extra operation. Instead of this transition function from Turing machine uh um option here you just can say I want to guess a number between zero and the current um current uh register count content. So you give me some value and I give you something non-deterministically chosen and again with the with the usual semantics that the machine somehow randomly guesses correct if it can right that's or it accepts if any of the possible computations accept kappa restricted means that you use at most a function of the parameter many non-deterministic steps so little Sebastian thought the other way around right I wanted the bound non-determinism on the polomial size. It turns out this is thorough. This is the correct way. This gives the clean theory. So if the parameter is small, very little non-determinism. Um I guess it makes sense because that's the part that gets exponential hindsight knowledge. Okay. Other than that it's uh what you would expect from an FPT algorithm. We can spend FPT time in terms of steps on this unit cost RAM.
4:37 The memory cells, how big are they allowed to be in the standard unit RAM? This is unbounded. Here it is bounded. But again, in terms of an FPT size. So the um that's the space. Sorry, this follows from the time. What I meant is is this one here. the content of each of these memory cells up here um is bounded by some function of your input size.
5:10 And this is this is meant in the sense of of max int if you if you want to think about it that way. So the largest integer you're allowed to modify um in these memory cells in one one step is is bounded as by this FPT type upper bound.
5:33 Okay. Um I think it's a rather reasonable definition. If you think about it with a sober mind, it makes very much sense that the parameter bounds the part that should go exponential that should be bound on the deter on the nondeterministic steps because these you may have to simulate by unfolding all possible computations and the rest is just a slightly more detailed formal way of stating what we said FPT running time. Okay, good. Um then based on that uh we can define another class of problems WP um don't ask about the name this is some it has a historic meaning and W stands for something uh weft but is a bit um it comes from a logic context and there it makes sense I think if you start from here the more intuitive explanation is just some name that's historically stuck WP uh is is a set of all parameterized problems that you can decide with exactly such a kappa restricted nondeterministic random access machine.
6:43 Okay. Um also sounds reasonable. So let's first do the sanity check that click can even be simulated in this that it's not too restricted now and uh indeed you can still simulate the brute force algorithm by non-deterministically guessing k numbers between zero and n that is another way of saying a subset of vertices of size k and then checking whether that's indeed a click is easy that's even just bounded in terms of k. So this is certainly an allowable time and uh the overall total time is even poly time. It doesn't need the ft part there. It just needed um so we didn't need this part right this we could have left out for click but in general it's allowed uh what we do what we do need is the non-determinism because we need to guess our solution the set of vertices.
7:42 Okay, so that's good. The class is not uh too restricted. Now let's look at a hardness notion. Again, we need some way to say that problems are as hard as every problem in WP. Uh we can do that precisely using our same reductions as before. So the difference why does this not give the same problematic definition as with parp is well we only say hardness means every problem in WP needs to be have a parameterized reduction to your problem. Okay. Uh what's less clear is we need some problem to do reductions from. What is a complete problem for WP?
8:27 And maybe this I should have turned into a slider question at some point. Maybe you can tell me why um P variable SAT is not a good idea for this here.
9:03 This is not a hard question. This is a question of whether you're processing all these definitions, which I think is hard enough. What do we know about P variable set? Is it in WP? How would you solve it?
9:54 Okay. Is that allowed in WP to nondeterministically guess the assignment? So you need as many nondeterministic steps roughly as you have variables. And is that allowed in WP?
10:21 Yes. Uh the parameter is the number of variables. We're guessing as often as K. So this is allowed. Okay, that's good. So it is in WP, but hold on a sec. That algorithm is also just in FPT by the same argument, right? Um uh there's in a way um with this parameter the whole problem becomes easy because you can uh you can use the same algorithm and uh I I guess the difference is the guessing is between two options not n a variable has two different values so this is um 2 to the k times some let's be generous polomial in the size of the formula and that happens to be an FPT. Whereas if that basis of the exponential part here involves the input size then it's it's not in FPT. So why is that a problem though? So this means um this is in FPT.
11:34 If that were WP complete then WP would not be larger than FPT. Okay. Yeah, these these are the questions that are simultaneously too easy and too hard. Um the the definitions get a bit confusing because there's many of them. That's the danger with presenting them in this succession. Uh on the other hand, the actual arguments are not hard that you have to do. So it's not teaching you a ton. So certainly P variable SAT is not our mother of all WP complete problems. So maybe there's a different one. And uh teasing out this difference between guessing between a constant number of options like true false assignments or something like a subset of n things. It seems to be crucial that we somehow guess bounded numbers um in this problem, right? And make make use of the fact that we're guessing out of an unbounded set. So what can you do with guessing k numbers out of n? Well, the obvious was a subset of of size K.
12:37 That's what we used before. And the the thing here is this doesn't very naturally translate to variable assignments. Um, but you can make it uh correspond to variable assignments if you're willing to bend the definitions a bit. And that's called weighted satisfiability.
13:00 um not a supernatural problem I think but it is in this case um a good intermediate problem maybe. So you have a boolean formula and this this threshold for the weight which is also your parameter and the question is is there a satisfying assignment where only k of the variables are set to true. So you're allowed to use as many variables as you want, but they should all be false in most well most variables should allow to be false for a satisfying assignment. Only K can be true. I don't know if that's natural, but it's a thing. Okay, that's what what weighted satisfiability means. The weight of an assignment is the number of variables that are one. And um sadly that's not enough uh to make it to a WP complete problem. We also have to go from boolean formulas to boolean circuits. Now let me do a twominut introduction to boolean circuits. It is really not a a very technical thing. Um the definition of circuits is easy. What is hard is the theory of what to do with circuits. And we won't uh stick our our toes into that yet. Uh it'll come back a bit later.
14:24 I think people know what a boolean formula is. You can write any kind of expression over boolean variables with the usual and or not and maybe some others if you want uh connectives or or operations. Um and a boolean circuit is almost the same but the point is that you can reuse sub expressions. So formally it's just a DAG where every vertex has a boolean operation. It may be allowed to have more than two incoming um edges. You can also restrict that. I mean you can always simulate this or with three inputs by uh two gates with or right. Same for and so that's not not my main point here. Um so every vertex is is such a a gate that tells you what to compute as an output. It has one outgoing uh arc that has the value of the computed function there. Then you have variables which are places where you can set zero or one and then you have um usually one output for for a decision problem. In principle it could also have several outputs. And of course this is it's precisely the kind of boolean circuits that you've done in in simulating processors, right? This is the same thing. Um maybe abstracted a bit. Um we don't care about delays. So we we assume if you put in values here instantaneously they propagate through the wires. There's no delay. There's no time. That's the difference to building computers.
15:53 Why do I say that we can reuse sub expressions? Well, we compute here the end of x1 and x2. And that and the result of that computation is used twice. This wire here splits which of course is a very natural thing in the circuit to do. But in a formula you wouldn't you would if you want to reuse this result you have to copy the formula and in the worst case that blows up the formula for a given circuit by an exponential. You might have to continuously double the occurrence of a sub formula. So in a way circuits can be exponentially more succinct. They can represent the same boolean function with a lot less hardware. Okay.
16:46 So that's that's all uh all that we need for this for here. Um if you take this satisfiability problem and put instead of formula circuit Well, let me say don't need to destroy the other problem There's this variant. That's the one that we look at here. This problem is WP complete as it turns out. Uh parameterized by the weight again. So the weight of the assignment that's the same, right? you have the number of input variables and you're allowed to set K of them to one. Okay, again the problem itself maybe isn't supernatural. Uh but I I still want to walk you through the proof because this is a rather insightful thing technique-wise.
17:47 Um the ultimate problem here again will be this problem. This problem weighted satisfiability and then also of circuits. This is too rich. There's probably no way to take an instance of this problem and encode it in the click problem. It seems that's asking for too much because circuits are very powerful, very expressive, as you'll see in a sec. And uh we would have to encode all possible circuits with this weird weighted assignment notion somehow in a graph problem like like click to get a reduction to show that that click is also WP hard which it isn't unless all everything collapses and that that's that's the problem with this theory. It leads to a nice hard complete problem. Uh but it's still a little too too hard. Uh let's still go through this proof though. Um first of all let us convince ourselves that um the problem is in WP. That's the first step. So we have to somehow construct such a kappa restricted non-deterministic random access machine for taking a circuit and a number k and checking if you can satisfy it with k things being true.
19:12 Well, this is this is easy to do because you can guess nondeterministically a subset of the variables up to K. You allow also maybe duplicate or maybe you allow uh one special value of not setting the variable to true. So uh at most K or equal K is not the not the problem. So you can guess a subset of variables to set to true. And then simulating the boolean circuit that is easy. You just do this with a graph processing algorithm. And you put your for a concrete chosen set of val variables that you set to true, you put these values here. Then you give the wires that come out of these a value. And if that wire splits, well, it gets the same value. So you process this. This is a a kind of um dynamic program on the on this DAG if you wish. At each gate, you have the two inputs. These are it's a DAG so they are computed before.
20:08 Then you compute the output that gives you the value of that wire. And so you can in a linear pass over the over the circuit compute the value at each wire including the output. And then that tells you whether the thing is true or false. Okay. In a way you're simulating with a computer built on base built on top of circuits its same uh building structure circuit. Of course, that's possible, but that's the boring part. The interesting part is the hardness.
20:42 Uh for the hardness, we have to pick an arbitrary problem in WP. And we're doing essentially the simulation like in in Cook Leven's theorem for normal SAT and NP. There we said, okay, arbitrary problem in NP. I have a Turing machine that solves that. Here, arbitrary problem in WP. I'm trying to solve that with my weighted satisfiability of circuits. And what you do is you assume you have this because the problem is in WP there's some kappa restricted non-rand nondeterministic random access machine M and you build a circuit that uh simulates that machine and again because this is the part that is a bit handwavy why it says sketch here. I'm not going to go through the full details here, but imagine this nondeterministic random access machine. It has memory contents at each point in time and it has some uh some program a fixed program that it runs. So it has a program counter where am I at which instruction and there's a a bunch of cases but you can essentially imagine how you build a compiler to turn that into a circuit.
21:56 And u the point here is that we we do this for a fixed input. We're given an instance after problem for this this kapa thing. So it is um there exists the machine that works for all inputs but we're given a specific input X. So we can hardwire that into the circuit. We bake it in and set it set all the inputs already to be the constants that this input X uses. Now this this N en RAM does a certain number of computation steps and uses a certain number of memory cells each with a certain bounded size for the numbers that are in there. So all of these are essentially um intermediate wires in my circuit at some point. I I have a a fairly large circuit. It's of of this uh FPT size. Okay. uh it's even some some polomial in this f of kp of n but with that I can I can have some intermediate state for the uh contents of the memory and I can have um gates that simulate the execution of of uh the operations if I do an addition well they I bake in the circuit for doing additions we're we're almost building a CPU here and I'm not going to tell go into the details because that's a a tricky thing to do, but it's possible. And what you get from that is a circuit of this size.
23:26 Again, this this part is very handwavy. You're um I'm I'm aware that this uh swallows a lot of details. What is not known? So the input x is not becoming variables. This is fixed values. What is unknown is for weighted satisfiability which of the um nondeterministic guesses of this non of this enramm are uh chosen which are set to true and this nam is allowed to do something in terms of the parameter many guesses and these guesses I'm encoding in a specific way namely in unary. So um the guesses each are numbers between zero and some ftt number. So I'm going to write down for each of these guesses f of k * polomial of n many variables. That's what this this is supposed to show here. This humongous number of f of k p of n is four. But you know um it's a sketch. So you have this blown up all the possible options for the guess. You have an extra variable. But the point is any valid computation will only set one of those to one and all others to zero.
24:51 That's the trick. Okay. And so the circuit simulates the machine on these guesses. If any way exists to set exactly k things to one then there is a way to make the machine without guesses except the input x and everything I need here is to simulate this in our in our circuit and that's what the weighted satisfiability for circuit does. So that's why I've finished here my ft reduction. Okay. Now a lot of magic is hidden in this step of how how to somehow simulate this general machine on a general circuit. The point why this really needs circuits is that uh if you were to try this with a formula in the style of cook leaven there we did this right we we took an arbitrary touring machine and said here's one one large formula that encodes this uh this was possible with a formula there by introducing intermediate v variables if you remember the details we had variables for things like After time t, the machine could be in this state and the tape could contain this and could was there is some non-deterministic way to get there.
26:10 But that means a lot of the variables were potentially one and there's no way to get this weight down to something bounded just on the number of nondeterministic steps because we need a way to kind of store intermediate results in variables. That's a way how formulas can be more more expressive without this exponential blow up in size by uh not duplicating the term that computes some value but saying this formula is equal to this variable and this variable I'm going to use elsewhere that I can do unless I'm not allowed to have more true formulas more more true variables.
26:53 Okay, bit of a subtle point maybe.
← Video 5-2: Nondeterministic FPT - para-NPVideo 5-3: Tail-Nondeterminism - W[1] →