0:19

Let me remind you the details of Papadimitriou's two sat algorithm.

Â Consider an instance of two sets.

Â Suppose it has n boolean variables.

Â The algorithm has two for loops.

Â The outer for loop,

Â it's only responsibility is to run log n independent random trials.

Â 0:35

In each iteration of this outer for

Â loop we're just going to do randomized local search.

Â So we begin with an initial random assignment.

Â We flip a fair coin independently for each of the n variables

Â to determine whether it starts out true or starts out false.

Â Then we get a budget of 2n squared local moves

Â in an attempt to transform this initial assignment into one that's satisfying.

Â 0:57

In each of these 2n squared inner iterations,

Â we first check if the current assignment is satisfying.

Â Obviously if it is, we're done.

Â So suppose the current assignment is not a satisfying assignment.

Â Then there's at least one, possibly many unsatisfied clauses.

Â Of them we pick one, arbitrarily.

Â It's a two set instance so this clause involves two variables and

Â if we flip the value of either of those two variables we're going to make amends

Â with this clause.

Â It will flip from unsatisfied to satisfied.

Â There's a tricky question of how do you pick which of the two variables you flip,

Â but we take the easy way out.

Â We just pick one of the two uniformly at random.

Â 1:33

If, at the end of the day, after these 2 n squared times log n local moves,

Â Papadimitriou's algorithm has failed to find a satisfying assignment,

Â it's somewhat arrogantly declares that therefore one must not exist.

Â What's clear about this algorithm is that it runs in polynomial time, after all,

Â we've explicitly bounded the number of steps it's permitted to take.

Â Secondly, it's clear that if there is no satisfying assignment, then the algorithm

Â will naturally fail to find one and correctly report that it's unsatisfiable.

Â 2:02

What's not at all obvious is the probability that Papadimitriou's algorithm

Â will find a satisfying assignment in instances

Â where at least one such assignment exists.

Â That analysis is the subject of this video.

Â 2:20

And again what's remarkable and surprising about this theorem is that if you think

Â about the most natural measure of progress for Papadimitriou's algorithm,

Â namely the number of clauses which are currently satisfied.

Â That number can actually go down when you make a local step.

Â By flipping the assignment to one variable, yeah you fixed the one clause

Â but you might screw up a bunch of others leaving you with an assignment that

Â seems worse in the sense that even fewer clauses are satisfied then before.

Â Nonetheless if you define the right measure of progress you can argue,

Â by a random walk analogy, that you are making progress over time

Â resulting eventually with a satisfying assignment.

Â Lets see the details.

Â 3:00

Each iteration of the outer for

Â loop represents a fresh opportunity to discover a satisfying assignment.

Â All of these iterations of the outer for loop are identical,

Â they just use fresh random coins.

Â So lets just analyze for

Â now the success probability of a particular outer iteration.

Â 3:17

We're assuming that this instance is satisfiable.

Â So there's at least one, perhaps many satisfying assignments.

Â Pick one, an arbitrary one, I don't care which, call it a*.

Â 3:27

Let's denote by a sub t the assignment that Papadimitriou's algorithm

Â is considering after t iterations of the inner for loop have completed.

Â So a sub 0, that's the random initial assignment with which we begin

Â this iteration of the outer for loop.

Â And then after we've done t local flips, that results in the assignment a sub t.

Â This is of course, a random variable.

Â It's a function of the random choices made by Papadimitriou's algorithm.

Â 3:52

Now the great idea in this analysis is to use the right progress measure.

Â Rather than counting the number of clauses that the current assignment satisfies,

Â we're going to count the number of variable assignments that it got right.

Â That is the number of variable assignments with which it agrees

Â with this reference satisfying assignment a*.

Â 4:28

Of course, if we ever get to the point where X sub t equals n, and a* is the same

Â as a t, then a t is itself a satisfying assignment and we're good to go.

Â The algorithm halts correctly.

Â 4:53

So suppose we are currently looking at the assignment a sub t, and suppose it's

Â not a satisfying assignment, then there's one or more clauses that are unsatisfied.

Â The algorithm picks one of those.

Â Let's say it's a clause involving the variables x sub i and x sub j.

Â So for example if it looks at the clause not x sub 3 or

Â x sub 7 then it's involving the variables x sub 3 and x sub 7.

Â So here's an easy observation.

Â Our current assignment a sub t is failing to satisfy this clause.

Â The reference satisfying assignment a* naturally is satisfying this clause.

Â Therefore, a* must give a different value to one of the two variables xi or

Â xj, than our assignment a sub t does.

Â 5:34

It is also possible, of course,

Â that a* makes different assignments to both of the variables xi and xj.

Â All we know is that a* satisfies the clause,

Â whereas our assignment a sub t does not.

Â 5:57

So Papadimitriou's algorithm is going to choose either xi or xj,

Â that choice is uniform at random.

Â And it's going to flip the value currently assigned to that variable.

Â Now the situation at which this is guaranteed to be good for us, is where we

Â gave the opposite assignment to both xi and xj, relative to the assignment a*.

Â If both of our value assignments of these variables was the opposite of a*,

Â whichever one we flip we are going to share one more variable in agreement

Â with a* than we did before.

Â That is, in our previous notation, x sub t + 1, the number of variables in which we

Â agree next time step will be guaranteed to be one more than it is right now.

Â The situation is more subtle when the current assignment a sub

Â t agrees with the reference satisfying assignment a* on

Â exactly one of the two variables xi and xj.

Â So for example, maybe the current assignment agrees with a* at xi, but

Â it disagrees with the reference assignment a* on xj.

Â Now of course, the algorithm has no idea what a* is, this arbitrary satisfying

Â assignment, so it has no idea which of the two variables xi or xj it should flip.

Â It just picked one of the two at random.

Â Now if we get lucky and we flip the value of the variable on which a sub t and

Â a* disagree then this is just like case one.

Â The flip causes the two assignments to agree on

Â one more variable than they did previously.

Â As a consequence, x sub t + 1 is going to be one more than x sub t.

Â 7:31

In the unlucky case we wind up flipping the variable on which we agreed

Â already with the reference assignment a*, then once we flip it we're going to

Â disagree on yet another variable with the reference assignment a*.

Â So in that case, x sub t + 1 is actually going to be 1 less than x sub t.

Â 7:51

And now at this point, I hope things are starting to look a little familiar

Â relative to our previous video about random walks on the non-negative integers.

Â There we again had a random variable, namely the position of the walk, and at

Â each time step it either went up by one or down by one, with 50-50 probability each.

Â So the situation here where the x sub t's is clearly not identical

Â to random walks on non-negative integers.

Â So the next quiz asks you to identify the differences between the random process

Â governing the x sub t's and your vanilla random walk on the non-negative integers

Â as studied in the previous video.

Â 8:35

If we think about two random processes the first one is your straight forward random

Â walk on the non-negative integers as discussed in the last video,

Â the second random process is the evolution of these random variables the x sub t's.

Â The number of variables on which the current assignment in Papadimitriue's

Â algorithm agrees with the reference satisfying assignment a*.

Â There are exactly three differences.

Â One we already pointed out.

Â In the vanilla random walk on the line unless you're at position zero,

Â if you're at any bigger position it's always 50-50 left or right.

Â In Papadimitriou's algorithm,

Â you might sometimes have a 0% probability of moving to the left.

Â A 100% chance of moving to the right.

Â That's when the algorithm zooms in on an unsatisfied clause in which the current

Â assignment a sub t happens to differ with the reference assignment a* on both of

Â the two variables.

Â Then it doesn't matter which of the variables you pick, you're guaranteed to

Â agree with the reference assignment a* on one more variable than before.

Â 9:31

The second difference is that when we studied random walks by definition we

Â always started at position zero.

Â that would correspond to this first random variable Xo = 0.

Â However, in general Xo will not be equal to 0.

Â In general it will be strictly bigger than 0.

Â Why is that?

Â Well remember, Xo is defined as the number of variables that have the same

Â value in the reference assignment a* and the initial random assignment ao.

Â So the only way that Xo is going to be zero is if you randomly chose

Â an assignment where every variable had the opposite value as what it is in a*.

Â And that's very unlikely to happen.

Â Generally you start with a random assignment, you're going to get lucky and

Â some of the values will be correct will be the same as in a*.

Â So Xo will generally start out bigger than zero.

Â 10:18

Here's the third and final difference, in the random walks that we studied,

Â the process by definition stopped exactly the first time you reach position n.

Â Now in Papadimitriou's algorithm, what is true is that if you ever get to

Â the point that x sub t equals n, then at that point the algorithm will terminate.

Â Why?

Â Well if x sub t equals n, that means that in the assignment a sub t

Â every single variable has exactly the same value as in the reference assignment a*.

Â Now a* is a satisfying assignment and

Â Papadimitriou's algorithm halts as soon as it finds a satisfying assignment.

Â So if x sub t equals n you found a* and you're good to go, you stop.

Â However, the converse is not true.

Â Papadimitrious's Algorithm might halt even though the current value of x sub t

Â is less than n.

Â Why is that?

Â Well remember x sub t measures your distance from

Â just this one satisfying assignment a* but nobody said that was the only one.

Â There might be other satisfying assignments out there in

Â the world as well.

Â And Papadimitriou's algorithm might well stumble upon one of them

Â before it finds a*.

Â So it halts the first time it finds a satisfying assignment.

Â And that can happen before x sub t equals n.

Â 11:30

So where does this leave us?

Â On the one hand, there does seem to be a strong metaphor between the distance

Â between the assignment in Papadimitriou's algorithm, and this reference assignment

Â a*, and the position of a random walk on the non-negative integers.

Â On the other hand, there's kind of a lot of differences.

Â Some of them are pretty subtle.

Â So what you've gotta be wondering is, was that whole analysis last video useful?

Â 11:54

Well what's amazing and what allows us to transfer the random walk analysis

Â over to Papadimitriou's algorithm is that every single one

Â of these three discrepancies between the two random processes only helps us.

Â It only means the algorithm's going to terminate even faster than we might have

Â suspected from the random walk analysis.

Â 12:12

So here's another way to think about it.

Â Imagine I force you to run Papadimitriou's algorithm under an extremely unfortunate

Â set of circumstances.

Â So first I give you a two set instance with just one, satisfying assignment.

Â So there's a unique satisfying assignment, a*, you're looking for

Â a needle in the hay stack, there's no way you can get lucky by halting early with

Â a different satisfying assignment.

Â 12:42

And finally imagine I further contrived things.

Â So that whenever you pick an unsatisfied clause to do a variable flip,

Â I force you to pick a clause where one of the variables is set the same as a a* and

Â the other variable is set the opposite of a*.

Â Well, for this kind of execution of Papadimitriou's Algorithm,

Â the correspondence between the evolution of the random variables,

Â the x sub t's and a random walk on the non-negative integers is perfect.

Â The two random processes are identical

Â under this worst case set of circumstances.

Â 13:16

Therefore, in the worst case circumstances, the probability that

Â Papadimitriou's algorithm fails to find a satisfying assignment, that is, a*,

Â within 2n squared steps is exactly the same as the probability that a random walk

Â beginning at zero fails to reach position n within 2n squared steps.

Â And we analyzed that failure probability in the previous video.

Â We proved its at most one-half.

Â That is the success probability is at least one-half.

Â Now if you look at any other circumstances other than the worse case circumstances,

Â Papadimitriou's algorithm is only more likely to succeed.

Â So first of all it doesn't start as far away from a satisfying assignment.

Â Second of all, there's other satisfying assignments it might be able to find.

Â And thirdly, sometimes it's guaranteed to make progress,

Â as opposed to having only a 50-50 chance.

Â So the success probability under any circumstances of Papadimitriou's

Â algorithm is at least 50% in a given iteration of this outer for loop.

Â 14:15

And now we're home free.

Â The probability that a given iteration of the outer for loop fails,

Â is at most one-half.

Â The probability that each of the log based 2n iterations of the outer for loop fail,

Â is then at most one-half, raised to the log base 2 of N, also know as 1 over n.

Â So the overall success probability of the algorithm,

Â is at least 1 minus 1 over n as claimed.

Â