Video 9-7: Schöning's SAT for 2SAT

0:03 In the next section, we'll again make um a little pivot to a very different problem. We're going back to uh NP hard problems for sure and try to see how far we can get with randomization even if we shouldn't expect to get down to something polomial time. um maybe we can do some something that's not so easy to do without randomization and I think it's it's true in this case also the strategy is much more versatile than this specific problem and the analysis technique also is much more versatile uh and so I think for that for that purpose rather than specifically the result about satisfiability this is this is worth uh having a look at uh we'll again use random sampling in in a specific way. What we've so far seen is if I'm trying to solve some problem and the solution is is tricky to construct in a targeted fashion, say perfect hashing uh perfect hash function, then uh I might try random sampling. If I know that there's many possible solutions, it's just a little tricky to get one specifically uh uh chosen.

1:12 Then we can uh just try this. Um, what we'll now use is random sampling when the object itself is rather rare or rather hard to find and we still want to uh somehow do something non-trivial to improve upon the brute force search that just tries all possible alternatives and surprisingly this is possible. What we'll need a bit to set up the methodology is a a tiny detour where the problem we're solving is not actually a hard problem. And that's the the two sat problem. Um you remember three uh as the np hard problem. Let's look at two sat sounds uh suspiciously similar. We're given a CNF formula where now we have at least at most two literal per clause not three. Why would that make such a big difference? Uh well it does. Um this is a problem in P. And the reason is that if you have two literals, you can rewrite the clause as implications.

2:22 It's just the the good old A implies B is the same as not A or B. And then you apply this with the right negations. So uh any such clause with two literals can really be seen as two implications also uh just from the logic u from the semantics itself if L1 was not true then to make the whole thing true L2 has to be true that means L1 not L1 implies L2 and also vice versa um what this means algorithmically is that we can represent the whole formula as a graph where the vertices are the literals which means the variables and their their negations. That's all the vertices in the graph. And we have edges whenever there's an implication coming from some clause that means one thing implies another.

3:17 And now we we can try to satisfy the formula in the graph by um picking certain vertices where we make that literal true. And we could try to just randomly pick a vertex, make that true, and then follow the outgoing edges, which give us implications. I also have to pick those vertices and set them to true. Um, and that has more implications. I'm I'm kind of going through the graph. Now, if I just do this planlessly, I might end up in a in a cycle. And then I could end up in a problem. The cycle might mean that some x i wants to be set to true, but then there's a cycle back to not x i which also wants to be set to true and then I'm not so sure what I should do. But if you think about this problem for a bit more, um you can show that if such a situation happens that there's a cycle from x i to not x i that's actually always uh an indication that the formula is just not satisfiable.

4:19 So if you ever run into this problem, there is a real fundamental problem that you're not going to get around ever. And if you don't run into this problem, you'll just find a satisfying assignment. Uh you can make instead of just starting at some random point and see where it leads you, um a more efficient uh way is to use strong connected components.

4:44 Um these can be computed in linear time with algorithms that you may have seen in undergrad. There's essentially a depth first search behind it. Uh in a clever clever combination of depth first search. So you can find um the strong connected components check if in any component you have both a variable and its negation. In that case you have a contradiction and you can just say there's no satisfying assignment. If that's not the case, then again you know from strong components uh if you contract every component into a single vertex the resulting graph has to be a DAC and so you can go through that DAC in topological sort order and satisfy all and and find a satisfying assignment by just starting at sources satisfying them and then following the implications. Um I've just run through this algorithm very quickly. If you've never seen this, maybe it's uh almost impossible to understand. My point was really just to say this algorithm is in P. We already know a simple solution. It's actually a linear time solvable problem. So, uh what comes now um is not so uh useful by itself. It's about illustrating the technique.

6:10 What can we do um to find a satisfying assignment if we don't want to invoke any kind we don't want to do any thinking okay no implication graphs no strong components that make my head headache anyways so let's do something random uh first of all we choose a uniformly chosen random assignment which most of the time is not going to satisfy the formula Um, but let's try either way. If if it currently does, then we're happy and we return it for sure. Uh, otherwise there must be some clause that's not satisfied. So, there's two literals and they're both false at the moment. So, I'm I'm going to pick arbitrarily one of them and make it true by flipping the uh assignment for that variable. And uh that's going to be my new assignment. Maybe I'm lucky. and that satisfies the formula. Probably I'm not and I just keep trying. It's a a completely mindless way of solving this problem. And uh in a way it it this shouldn't be allowed to to be successful.

7:21 But again, the two problem is tame enough that it actually does succeed in a in a way. First of all, what does succeed mean? If I ever find a satisfying assignment, then I'm clearly proving that the formula is satisfiable. Uh if I do this for a certain number of repetitions, we'll come back to this confidence parameter. Then uh all I can say is that probably the formula is not satisfiable, right? It's uh it's a Monte Carlo algorithm.

7:53 Now um the running time is not hard to uh analyze because uh these are just explicit loops. So you're going to run through things a couple of times. Um the the number of loops say the confidence we put to some constant for now the number of loops is essentially quadratic in the number of variables and all we do inside is is pretty cheap. So it's not it's not as great as the uh welloughtout linear time algorithm but at least not super far away. And indeed we can prove um if we're given any two set formula and it's unsatisfiable then we'll uh always output not satisfiable. Um but if it is satisfiable then uh with high probability in terms of this confidence we'll find a satisfying assignment. Okay.

8:48 And yeah the uh um overall running time I didn't even put on the slide is there anything interesting happening here so this will take linear time in the formula if you do it naively so I guess It'll be k^ 2 times the confidence parameter and then times the length of the formula say n for that.

9:39 But the interesting part is to analyze this. Okay. Uh the first statement we're not going to prove that's obvious. If there's no satisfying assignment, I can try searching as long as I want. So clearly I won't find one. Uh the interesting part is to show that um I have a good chance of finding a satisfying assignment if there is one.

10:26 that means there is at least some alpha that satisfies and I'm going to stick with this worst case that there's a single assignment making the formula true. In general, it could be many, but we'll we'll just fix this one. And uh everything will be analyzed in terms of this worst case assumption that that's the only one.

11:05 then uh the algorithm is obviously running in in uh iterations. So it'll compute different assignments in the different time steps. So let's say alpha t is the uh variable assignment and t clearly runs from one up to this confidence Okay. And so the interesting parameter will be how far are we in these assignments that we try away from the satisfying one. And specifically what we'll look at is just the Hamming distance of our satisfying assignment, the single one that we pick and what we currently have. That's a random process. And you can go up and down, you can go either, you can go whatever, right? Uh heming distance just means positions where they differ. So the number of variables where they differ um and so let's make a few obvious uh um observations. if we ever have um okay is to stay consistent let's um flip this around so we use k minus the distance then it's a a positive thing to improve so k x kxt is our current the number of uh variables that we correctly guessed Um if we reach K then we're happy we found our satisfying assignment and so then we can stop. Uh otherwise we're going to keep trying. So what the algorithm does in this case is it binds a clause that's not satisfied and picks one of the literals and flips the assignment. So I'm going to change the variable assignment of a single variable. That's going to get my x t + one either one better or one worse. I don't know which one.

14:17 Of course, at the boundaries, if I'm if I'm somehow unlucky and I made every variable zero, then the minus one is not possible. But it's always going to be true that one of those two options is what happens. Um now what are the probabilities for these two uh outcomes?

14:42 Sorry, XT + one. Let's uh focus on on the good things in life. So what's the probability that I'm going to end up with the next uh with a uh an improvement? Um If you look at what what we're doing, we have an unsatisfied clause. Currently, these are both in the wrong assignment. So, there's there's different possibilities. Uh what alpha can assign to these variables. We could have one of them guessed, right? Or we could have both. Uh we could have none of them guessed right. Right. So um in this unsatisfied clause C could have two incorrect or one incorrect.

15:49 If we guessed only one variable incorrect then the probability 1/2 will improve with probability 1/2 we improve. and if both were incorrect then we always improve. Amazing.

16:19 So with probability one improved. So we don't know which of the two happens. All we can say is with probability at least 1/2 we're going to see an improvement. And that's why two set is easier. Uh if you think uh we'll we'll apply apply the same trick to three set later. There you have three literals. That's three three little literals and you don't know in the worst case you could have just one of them guessed guessed right or guessed wrong and you have to somehow hit one out of three. Um that's going to be less likely. So it's less than 1/ half probability potentially to guess to make an improvement. Whereas here we have at least one half. And so at any point in time in two set it's more likely to improve your assignment than to make it worse. And that's uh I guess intuitively is is making it much more likely to see improvement after improvement. Okay, we'll we'll come back to that if uh if that didn't help you too much.

17:26 Um also uh the starting point x0 is any number between zero and n k. We don't know where we start. Um in the worst case we start at zero. Yeah, it won't ever get worse than that. And so we'll we'll analyze this this worst case in the following.

18:07 Okay. Um how how are we going to do that is first of all we note this these transition probabilities what happens to our assignment and particularly this random variable of how many variables we have already assigned correctly. This is a markoff process because all all that depends all that comes next depends only on how many I've guessed correctly so far. In the way I've described it here, uh that's true. You can you can say it's a mark of process for the entire assignment. Um but for the behavior of how many we guessed correctly, uh it only it only depends really on the previous XT.

18:49 Um or at least uh we can say the true process is never going to behave worse than a markup chain that only looks at the number.