Video 9-8: Schöning's 3SAT algorithm

0:02 In the next section, we'll look at uh uses of randomization for solving NP hard problems. In particular, um we'll look at the threes problem. And so in comparison to the previous chapters, um here we're really trying to find a random object that's very rare, namely a satisfying assignment. At least it could be very rare if you're given a a formula that is satisfiable. it might be very hard to find the the single satisfying assignment in the worst case. And we'll use random sampling for that. As a warm-up, we'll just do the two set problem. And um I discussed this in in more detail previously. So um maybe just the the quick run through and uh it does make sense to keep that part of the old recording. uh so three set is np nplete but two set isn't because you can uh rewrite the problem as a graph problem two set clause is uh equivalent to two implications and so you can formulate this on a graph as essentially uh finding uh cycles of implications and uh whenever you have a cycle that includes a contradiction then you're doomed and you can show that this is a characterization formula is satisfiable if the two sat formula if and only if the strongly connected components don't contain any contradiction and you can turn this into a linear time algorithm.

1:31 So we're not trying to solve this problem any better. All we're doing is a warm-up for what's coming for three set right after this. Um but it's it's uh useful to illustrate the tool especially for the analysis to uh look at this simpler problem first. Um the whole design technology design methodology is called local search and it's much more broadly applicable than than this specific example. Uh but also as you'll see in this in the threes version it's there's some parameters to tune and without some idea for the analysis it's usually very hard to tune them in the right way. For two set uh life is easier. You can just take a a uniform randomly chosen assignment at the beginning and then we locally improve it. What does that mean in this specific case? If the formula is not yet satisfied well I guess if it is it's the easiest case and we just stop. But if it's not, there must be some clause that's not satisfied. It has two two literals.

2:36 Uh if it's not satisfied, both of these are false. So I'm just going to pick a random one and make it true. That makes the clause true and hopefully gets me closer to a satisfying assignment.

2:48 And I keep doing this for uh a certain magic number of times. And uh if I've not not succeeded after so many attempts to locally tweak the assignment, then I'm I'm going to declare this is likely not satisfiable.

3:04 Now, uh this number of repetitions is crucial otherwise you don't get a good guarantee in this in this case here. Um to summarize the uh the properties, if the formula is unsatisfiable, we never accidentally report on a satisfying assignment. That's clear. But if a formula is satisfiable, we might still not find an assignment if we're continuously unlucky.

3:31 And so we have to talk about uh how likely that is. And um the running time is is an easy analysis because it's basically just the number of loop uh iterations. And I've I've put gener generously linear time for checking the formula each time without even trying to be very smart about it.

3:55 uh the critical part is to prove claim two right that if I have a satisfying assign u if I have a satisfiable formula I find some satisfying assignment with this probability 1 - 2 to the minus confidence which is a parameter we give so we can make it extremely likely to find it if we keep going for a while and you see that this is is a relatively good dependence if you want to uh have the error probability ility you just have to double the number of iterations.

4:29 How can we prove this? Um we start with some random initial assignment. Let's call that alpha 0. And then uh we do in each iteration if we're not yet done then life's easy. Uh we flip one variable in this alpha t to become to get the next assignment alpha t + one. And that's all we do. We say in the algorithm we make one of the literals true but it really means just uh flipping the assignment of one variable. Uh what we'll do is we'll analyze this is uh I alluded to this last last time but um a bit more cleanly. The algorithm itself is complicated because we don't exactly know how many satisfying assignments there are. So it might stop early. We don't know exactly if in a certain literal in a certain clause I could have picked either literal and made progress. So we'll analyze a simpler random process W which is uh certainly running for longer or never never shorter than our actual local search but which is easier to analyze.

5:33 So we'll get an upper bound on the running time by analyzing a process that might run for longer. So in several places we're making worst case assumptions and thereby creating a process that's a little bit further away from the original algorithm but uh becomes easier to analyze.

5:52 And uh the first the first such uh simplifying assumption is that if the formula is satisfiable, we know there's some satisfying assignment. Let's assume there's just this one. Or in other words, you have a specific satisfying assignment in mind and you want to hit exactly that and you don't accept any others. Let's call that alpha star. And uh w will only stop if we hit exactly that assignment.

6:18 Um now we can measure the progress we make towards hitting exactly this assignment in a much easier way. Namely, how many variables does the current assignment alpha t have in common with this satis with this assignment alpha star? that's expressed via the Hamming distance, but really it's how many variables do you assign to the same truth value and that's a random variable that changes over time. Um, and this is indeed, uh, yeah, it's a it's a number for now.

6:55 Now um local search starts at the random alpha but we can again make a worst case assumption and say our w has to start at the worst possible uh starting point which is the complete opposite of alpha star. So we start at the negated uh position every variable is set to the opposite truth value. Then initially we have no variables in common with the uh alpha star assignment we were trying to to hit. Then if we look at a specific clause if it's not satisfied then um what we know about our current assignment and alpha star is that they have to differ somehow and uh they might differ in uh so so alpha star makes this true alpha t makes it false but it could be that even alpha star makes only one of them true it's not it's not it's not clear uh by how much they differ but I certainly have to change one variable otherwise alpha star couldn't satisfy this but uh it could also be that I have to change both this is just we don't know uh the case that I have to change both is the good case because then my uh my random flip will always make progress and will always increase my x the number of variables I'm guessing correctly. So, it sounds like the case where we're further away is is the bad one, but if if I picked the right clause, it's actually the good case because I'm guaranteed to make progress. Uh, but in the other case, um, if they if the assignments only differ in one of the two variables, I only have this uh probability one half to pick the right one in my local search. And so the next time where we use u a worst case assumption is that we'll always have this bad case where we only have a probability of 1/2 to make progress.

8:48 Okay. So several cases where we pick worst case assumptions. We have a single satisfying assignment that we're trying to hit. We start in the worst possible state and we're only making progress with the the lowest of all uh possible alternative um scenarios.

9:11 That means um W makes a correct flip with exactly the probability 1/2 and the flip side if it makes the other choice it flips a variable into the opposite. So it decreases x by one. Right? So these these are the two options. uh in each stage. If we're not done yet, then the new um the um number of variables that agree in the next time step can go up by one with probability 1/2 or can go down by one with probability 1/2. Um and uh there's only these boundary conditions. Now with this with this definition, this is a markoff process because the probability of what happens next depends only on the current state. If you want the original algorithm is also a markoff process but then you have to take the full assignment not just the number of variables that you guess correctly but you have to take the full assignment into account and is uh I don't I don't see how you could analyze this. Uh but this mark of process with only the number of correct variables is very simple. Now it's just a random walk where you go up with probability 1/2 and down with probability 1/2 and then it has a boundary condition at zero. You can't go below zero. So you you're stuck there and have to bounce back basically.

10:29 And um there's an absorbing state. If you hit K all variables assigned the same way, then you stop. So if you keep running this random walk, it will eventually stop because there's no way it cannot. It might run forever around, but that's with probability zero. It will almost surely hit eventually this state because of the reflective because of the uh well because of the probabilities. Okay.

11:00 Uh so uh how can how can we prove this? How can we analyze this random process? Uh we'll we'll get back to this. Um I'm showing the analysis in a slightly more general form than we needed. One because while we're at it, you can do a more general form and maybe it's useful for some other problem, but also it will be useful for the subsequent problem.

11:25 Uh the key here is uh what to analyze and uh we'll we'll keep things simple by looking just at the expectations. uh the key quantity will be this y i which is you're currently in this state i of the mark of process now there's uh you can go up or down with probability 1/2 each right so I'm currently at this point and you can go up or down blah blah blah uh eventually I might reach this absorbing state k and so the quantity we're interested in is the expected number of steps until I reach this this state.

12:10 Uh and it turns out this is this is well defined and can be computed. Um and it is a in a way a recursive equation. So yi is indexed by the starting position.

12:22 Now we can say a few things. Y k is zero because we're already in the absorbing state. There's uh deterministically the end. Y0 all the way to the left. This is the uh the bounce back state. You can only go back to state one from there. But you have to uh spend one time step. So the expected number of steps to reach from y0 the absorbing state is one for the first step plus whatever it needs to get whatever it takes you to get from y1 to the absorbing state. And this works these equations work because these are expected case expected values. So they're linear. it this um y1 might do many more steps but uh we certainly need this step one and so it's it's indep it's it's uh it's linear in well the term for y0 is is linear in the expectation of of um from from state one um there's also a lot of independence in this process but we're not even exploiting that at this points. Then the general form at yi we we have probability 1/2 to go up or down. Um you can write down the equations for a general probability where this is some probability pi and then you have probability qi to go down and the whole first step works in full generality.

13:54 So probability pi to go up, Qi to go down. And this is for all I between these two. Uh okay. Now, how can we solve this? It sounds like a it looks like a not so nice recurrence. Uh but there's a cute trick that always works in this case. Um first of all we do a curious thing. We write yi as pi yi plus qi yi which is the same because these sum to one. And then I use the recursion here on the other side. And I'm uh rearranging terms. So um get uh the yi + one on the other side then or rather this guy goes to the to the other side here then I have p i * y i + 1 minus y i that's this this part and then there's these two that form into this part on the other side and there's the minus one which just from the one step that we have to take and if we now divide by pi then we get a clean recurrence for the differences between the y i's and I'm giving them a name here so uh y i dot sorry there's the i missing y i dot is just the difference y i + 1 minus y i and uh with a bit of abbreviation then we get a relatively clean uh recursion here. Y I Y do I is a I Y dot I minus one plus B I and so if you look at at this recurrence that's a nice telescoping recurrence. This is about the easiest form of recurrence you can have. you can just insert the recursion again and again and unfold it um until you reach the boundary condition for for y0 dot y do.0 zero again to say where we have the value given.

16:15 Okay. So if you unfold this um then you get this uh this general solution which is um you're you're collecting factors of ai until you reach the boundary condition. That's the first part. And then you also have to collect all those tall terms bi that you collect along the way. And so you you have a sum for all the levels in the recursion. You collect the prefactors from recursively inserting and then you have your BI. We don't actually need that full general form. It's just uh cute that you can write it down. Um there's one more step that you can do in full generality which is summing up all the y dot eyes is actually a telescoping sum because each y dot is the difference of one term and the previous. So if you sum up all those you get every term with a positive and a negative sign except for the first and last.

17:20 And so uh summing up all those y doj gives you just the difference between y i and uh y z. So you can rewrite y0 as uh yk which we know is zero minus the the sum of all those y dots and these we have in explicit form.

17:45 Okay. Um maybe this form is not explicit enough to make sense of it. But if you plug in what we know about our P's and Q's again, okay, I have to go back here. Um, AI was just qi divided pi. BI was minus one divided pi. Okay, this is once you know p and q, um, these all become the same. Ai is all one and the bi's are all minus2. So in particular all those products are just one. They're just gone that means um from this from this uh uh from from this formula you get that y do I is just minus 2 i minus one. And if you plug that into that formula here, then you get an expression for y0, which was the expected number of steps it takes you from the worst possible state to the absorbing state. That's what y0 is.

19:07 Uh you may have seen this curious sum here. I'm I'm skipping the the algebra, but it's uh the sum of the first odd numbers, which is always a square. So the cool graphical proof is that's one. Then if you add three, you do it that way. If you add five, you can do it that way. So it's always always a perfect square. Well, what does that mean? We need k^ squ steps in expectation to get from pretty much anywhere to the absorbing state because y0 is the largest. All the other yis are just smaller because they're already closer to uh the absorbing state k. If you care, you can exactly compute what their value is. But if you look at this formula, you already see it will be just uh k minus i^ 2. So our uh our random walk w reaches this this um single satisfying assignment that we picked out in expectation after k square steps. K is the number of variables.

20:13 And so also uh the number of iterations that it takes this local search to reach alpha star in expectation is at most k squ because we made these pessimistic assumptions along the way several cases. And uh from that it's the standard machinery. If you want a success probability you use marov's inequality. So the probability that we take two times the expected number of iterations is at most 1/2. And then if we do even more iterations, you could try to insert that here, but that gives a worse bound. Instead, you're grouping two karations as one random trial. And then the probability that all of those fail if you do confidence many iterations of these trials the probability that all of those fail is 2 to the minus confidence and that's where we where we get the success probability from.

21:16 Okay. So keep in mind um the picture here um about this uh this random walk maybe that picture if you have a random walk with a bouncing state zero you bounce back from zero into the positive states and you have an absorbing state at K. You can calculate the number of expect the expected number of steps it takes you to reach the absorbing state in pretty much full generality. And there's uh there's more to be said. Uh you can also take from from this k squar the intuitive fact that if you uh take an unconstrained random walk that goes up and down with probability 1/2 each and you let it run for n steps it moves roughly away from zero by square root n. That's roughly the same same argument. Okay. Okay. Um so far so good. So we can solve two sets. Amazing. We could already do that with classical algorithms. Uh so how much can we push uh this idea further?

22:33 And that's where we um where we come back to threes. Let's apply the same idea and see what changes. Well, the obvious thing that changes is we have three literals, not two clear. Uh the key point that made the two-sided algorithm work was that the probability to move closer to a specific satisfying assignment was at least 1/2. And then we were pessimistic and said it's exactly 1/2, but that's what it what it was. Uh for three set, this is going to go down to 1/3 because we have three literals and in the worst case, we're guessing two of them already correctly. We'll be setting them to say to the right truth value for the rest of the formula even though it makes them false in this in this clause. And we have to pick the right out of the three to flip the uh assignment. And so that's probability 1/3. There's of course all the other cases where we're more lucky um and where the probability of success is higher, but in the worst case that's the best we can say.

23:40 Now, is that a big deal? like a a third and a and a half sounds not too big of a a difference. Um you see how how big a difference it is if you plug it into this random walk analysis that we've done before. So that's just copied from the previous slide this general expression for the white dots. And now we have probability P is just a third to go up and with 2/3 we go down. And intuitively you already see where the problem is. This is a random walk with a drift towards smaller numbers and we ask it to reach a large number that's going to take a lot a lot more trial and uh exactly how much we'll see here. So we can calculate our A and our B again. Um I guess here the B bis's uh same as the A's. They all all this all constants. But here a now is is a two.

24:36 So all these products are no longer one. They're powers of two. And if you plug that in so we get for for y i. This product turns into two to the i. The other product here turns into 2 to the i minus j. And then we still have this sum to evaluate. Uh so if you uh you flip the order of summation or you shift you shift the summation a bit. Yeah, you reverse the order of summation and shift it. Uh then you're summing up the first powers of two which is the next power of 2 minus one to the i minus one. And so you can combine these. Basically what what remains is an exponential dependence on i. So also it's negative. If you plug in this uh um if if you undo the the differences then what you get is the sum of all those uh y i y js. These are exponential in i and we're summing them up. So again we get the next larger power of two with some constant factors in front.

25:48 And so now it takes four times to the decay steps roughly to get from the worst possible state to the absorbing state. That's not so great because in time roughly two to the K, I could have just tried all assignments, right? There's not more than two to the K possible assignments. And so this random process takes four times that long in expectation to reach the absorbing state. which means this uh just keeping this local search running is not going to work. Uh the drift is too strong. It pulls it down away from your satisfying assignment uh so much that essentially you would have to spend more time than the brute force algorithm to get gain anything from it. So that that doesn't work. Uh but what we're neglecting here is that we're we're also uh starting at a random point initially. We pick a random assignment and then we start locally modifying it. And if we're lucky then this initial assignment is not so far away from our alpha star and we might have a better chance of reaching that absorbing state.

27:07 And that's what we're trying next. So if we wait for too long in the local search, we're only going to move away from this uh satisfying assignment.

27:14 So instead, um that's the point I just made. We're starting at a random point. Instead, we're using these local searches for a little bit of an improvement because we can't really expect if you just start with a random assignment to magically hit alpha star. That's exponentially unlikely. But we can guess some random alpha and walk a little bit around for a while in the hope that that might move us by random chance closer to alpha star. But then we keep just trying with a new random alpha. That's that's going to be the algorithm. And by balancing out the two parts, how often do you repeat the overall process and how long do you try local modifications, you can overall improve the running time a lot. And that's what what people usually say if they if they say local mean what they when they say local search is not that you just randomly modify things and hope for the best but you balance out restarting with a random starting point and then local searches away from that point.

28:24 Okay. And uh that's the final final algorithm that pops out of this where there's some curious constants in there that will pop out from the analysis and you can you can justify them um post talk. Uh intuitively the algorithm does exactly what I said. It's it picks many random starting points, keeps walking for a bit and if that didn't work, it gives up and tries a new random assignment.

28:54 Uh we can have this confidence parameter um which is no longer used. Sorry. Uh I modified this um so that the the statement will just be about probability 1/2 to be um okay I didn't modify this this should be just 1/2 because confidence is no longer part of this um is the same argument as in in the two set version. Basically, a a single one-sided aromonte carlo version where you just need probability one half to be correct uh uses that many repetitions on the outer loop. Each time you choose a random assignment and you walk for threek steps randomly from that specific assignment and the walking is the same as before. If if it fulfills the formula because we're lucky, then we're done. Otherwise, there's a clause with which is unsatisfied and we pick at random one of the three literals and make that one true. And that's that's the local search step. Okay, so the the key constants here are a relatively small number of local search steps, just 3k, no squared anymore, and a huge number 4/3 to the k uh of overall repetitions of the process.

30:39 Um let's see how we can analyze this. uh the the second part uh this should be ah I see uh I think 2 doesn't match but okay um we'll we'll basically show that we have probability 1/2 to be correct with the algorithm as stated here and Then if you want this one minus two to the confidence and there's a minus missing as well.

31:28 That's the same argument as before. So you just treat it as independent repetitions and the probability that all of them fail is is just 2 to the minus confidence 2 to the minus number of repetitions. Uh also as before if if the formula is unsatisfiable we're not going to make suddenly claims about a sat a wrong satisfying assignment. The interesting bit to show is if the formula is satisfiable then uh we will find us an assignment and we'll make the same worst case assumption as before. there might be a single satisfying assignment or in other words we pick one and then we calculate the probability that this algorithm hits exactly this predetermined satisfying assignment and we want that to happen with probability 1/2 and so we uh we need a claim in between which looks at one run of the local search. So um we will analyze this probability that the uh local search which is just this part.

32:48 One iteration of this will find our alpha star with a certain probability and that probability is very small. Now you see the uh the form of this term is already reflected in the number of repetitions. Maybe that last part will not be very surprising. But how how do we get to this weird kind of probability?

33:13 The uh proof is taking a similar um similar analysis as before. We we'll analyze the number of variables that we're currently correctly guessing and we make some um pessimistic assumptions along the way. Um but we have to work slightly different. So with this uh argument from before, we would only get a a two to the uh if we're currently wrong on on i variables, we would get two to the i as the probability to or the expected steps to reach the absorbing state. That's not good enough. So instead, we're doing um a different analysis. First of all, we start with a random assignment alpha in each of these local search steps. And what's the expected or what what's the um distribution of the number of variables that we guess correctly initially? Uh if we start with a random alpha and we compare it with some fixed alpha star, each variable is with probability 1/2 independent of the others guessed correctly. Right? So that's just a binomial distribution and we know what uh what that looks like. Uh we'll come back to that.

34:27 Now conditional on having a certain value of X um we'll have to climb up a certain number of steps with our local search to reach the absorbing state and we'll analyze a very very specific case namely we're starting at at X we want to reach K or let me draw it a bit more graphically as kind of a levels. We're at level X and we want to reach.

35:09 So now I have a dimension for time. This is X. This is K. So that's the number of uh set of of correctly guessed assignments and this dimension is time. So I'm uh initially starting here as a random variable. We'll we'll get to analyze this. I have to eventually reach that thing. So, I can walk up or down.

35:37 I'm actually more likely to go down as we know. But maybe I'm lucky and I eventually reach this this part here. Um I'm continuing to draw to draw the dots here for a specific reason. Uh it's easier to analyze a very specific scenario. So, First of all, we need to climb k minus x steps because that's this distance a little x as I wrote it here. That's for sure. Um in general is it's a bit tricky to analyze how likely that is. But we'll pick a specific step. We'll just look at 3k steps at most. But in the analysis, so 3k is from the from the algorithm. It keeps trying for 3k steps. U is at most k. Uh we'll analyze only the first three * u of them. So in that picture if you take that height three times so flip it down that's where we stop reu.

36:49 Now uh what I can certainly say if among those first three times u steps there's uh two * u steps up at least then I'm going to end up here above the line if you want or I'm going to be at this line. So we're we're again um analyzing a simpler process. We're we're analyzing a process where I'm not constrained by this absorbing state K. I'm just walking for three times U steps up and down. And I'm asking how likely is it that two U of those steps go up. If they do, I'll certainly end up hitting the absorbing state in the actual process. But here I'm I'm kind of pessimistic again in keeping the process going. Even if I hit before I'm I'm going to ignore it and walk keep on walking. But if I do two two * u upsteps I'm certainly hitting uh the line k at some point. So that's going to be a lower bound on the probability.

37:54 The probability q meaning um I have u steps to walk up will be uh well the probability that we have two u upsteps in three u randomly chosen steps and we'll upper bound we'll we'll lower bound this by the probability to have exactly two times u steps. So we're uh seemingly throwing away a lot of probability mass but because of uh the binomial distribution. So we're in this the binomial distribution has this this nice peak around the expect maybe more like this right for larger ah looks ugly maybe like this. So we're um we're betting to be close to the value k already. And so the probability of being to the right of this is actually u mostly dominated by this leftmost point because it falls exponentially in this in this far end of the tail. Well, uh that's the intuition, but of course it's always true. If you make the event more narrow, then the probability is going down. And the probability for this event, we can nicely write that's just the probability of uh out of the three U steps to have exactly u that go down. So 2/3 to the power u 1/3 to the^ 2 U. It's a again a binomial distribution.

39:27 Okay. Now, this we'll have to analyze a bit and we're using something here. Maybe this is of general interest. I don't know. We've used Sterling's approximation many times. But here we need a a slightly stronger one where you have an um explicit upper and lower bound. Um it's called Sterling Robbins inequality. uh is you can write it as an equation where for every n you have some some value here in front. So this is the the typical term from Sterling's approximation. And then you have some term uh in the front here where um sorry this is the n is is up here doesn't make sense. There's some some value rn which is tightly sandwiched between two terms. Um and then it's too small and you can also bound this e to the r n step uh term between one and two and we'll we'll only use use this part. So you can say we replace this e here with an interval one and two and then I would take the equality to mean that this is in this uh interval that you get by multiplying this with the the constant term. Okay, so it's an upper bound for it's an upper and lower bound for um factorials which is very close to this and only differs into constant and the difference is only two.

41:12 Uh we can use this to bound the binomial coefficient. So this is by definition these uh factorials and then we use on the uh numerator we use the the lower bound version and on the denominator we use the upper bound version. Uh what's left is um the the e to the n parts they cancel out because there's three u on top and u and two u more on the bottom. They just go away. the uh n to the n part. That's the 3 u um up here and the u and 2 u here. But then again, the 's cancel because there's u to the 3 u up here, u to u u to the 2 u. They also cancel. Uh so all that's left is is this 3 to the 3 U 2 to the 2 U and a certain constant C up front which is uh coming from these um two square<unk> pi and I'm plugging in the the upper bounds for the denominator.

42:23 Uh all that we need is is some number and it's greater than 1 12. Okay. So it's a fairly uh fairly tight bound for this um binomial coefficient but still has these exponentials of course.

42:41 And if we plug that in here, you see the most of the the threes all just cancel because you have 3 to the 2 u 3 to the u. Those go away with the 3 to the 3 U. The c /<unk> u stays and the two to the u is left because we have two to the 2 u here and only two to the u up here. Yeah, I mean it's it's just road calculation. Um not much magic needed. The key ingredient is this this tight bound on the factorials. Then the rest is just doing the math. So what have we learned? the probability to have this many number of upsteps despite them being less likely, right? It's still one/ird only. Uh we can still get a lower bound for this probability. It's exponentially going down with U. Not too unexpected, but there we go.

43:39 Okay. Uh now this was for a specific U um where we start with uh k minus u where we still have u variables u variables are incorrectly guessed we have to average this overall possible values for u if you want and uh the probability for that that's the binomial we get from picking the random assignment. So that's well of course first rewriting um to get the the terms nicer but really it's uh this probability is from the binomial distribution. So you have this uh k choose the value 1/2 to the k. The uh probabilities for the positive negative outcome are the same. So it's just 1/2 to the k. And I've split off from the sum here the term for uh u equals zero.

44:42 uh because for for u equal so yeah if u equals zero that means we've guessed all variables correctly and then we stop immediately so that term we can separately deal with all the others are are here and uh so now we plug in what we know for q that was this term um Then we um move the sum inwards. So here's a few things that don't depend on u. This doesn't depend on u. And the um the square root u we just um say this is always smaller than putting in the largest value of u in the sum. So we pull these two terms out. Um and uh we sum from well what's left the k choose u 1/2 to the u. Now there's two more tricks. Uh we let the sum start at zero again whereas this was at one. So we subtract the first term to compensate for that. And I'm uh pre pre- knowingly inserting this uh factor one here. And then if you if you stare at this sum for a bit, maybe you recognize that this is an instance of the binomial theorem.

46:07 Binomial theorem in general is a way to evaluate a plus b to the power n and it's evaluated as a sum. We exactly have this binomial coefficient. So this matches exactly that shape here where a is 1/2 and b is one. So we can use the binomial theorem in reverse here and we get 12 + a + b 1/2 + 1 to the power k. That's a cool trick, right? Uh and that's that's where the the uh three halves comes from.

46:43 And the three halves and the 1/2 to the k they combine to three quarters to dec. And the one is essentially bigger than this. So you can bound that away. And what's left is is this this nice term. And then we use that constant C was less than 1 over 12. That's where this 12 comes from. And that proves our claim which everyone has forgotten by now what it was. The claim is that one round of local search succeeds with this probability at least. And that was what we computed. uh Q is the probability to succeed in in total. We've started with QU. What's the probability if I know where I'm starting? We lower bounded that and then we lower bounded the uh total um expectation.

47:42 Okay. So um with that we're almost done. the expected number of uh independent repetitions before we see a success. Standard geometric distribution argument. One trial has this probability to succeed. That's Q. Um if I uh repeat for one over Q successes, I expect to see at least one one success. Uh this the lower the bound here is not um respected. there should be one at most one over Q. Um but that's the exp that's that's an upper bound for the expectation and so uh we can use uh marks inequality in the standard way again we use two times the expected value even more actually and that's this this lovely number if we keep trying for that many local search repetitions the success probability is 1/2 at least okay that was that. Um, now you see how uh maybe let me just go now the theorem was was not stated properly. Anyways, uh you can still see the the running time is essentially this, right? It's uh if we're if we're uh not too too strict, it's essentially 4 over 3 to the k as opposed to 2 to the k, which is a a massive reduction in the base of the exponent.

49:17 Now, if you want higher success probability, you have to do this a few times, but it's it's basically a a con a factor that you have to do it um at most a polomial factor and then you get with high probability. So uh this is actually a a substantial reduction of the style that we've tried to get with fixed parameter algorithms.

49:39 And so randomization here makes makes this kind of reduction of the exponential growth much easier.