Now we'll see how our understanding of basic properties of random walks on the
non-negative integers unlocks the analysis of Papadimitriou's Algorithm,
showing that randomized local search yields a polynomial time algorithm for
the 2-SAT problem. Let me remind you the details of
Papadimitirou's true set algorithm. consider an instance of two set it has n
bullion variables, the algorithm has two four loops, the outer four loop its only
responsibility is to run log in independent random trials.
In each iteration of this outer four loop we're just going to do randomized local
search. So we begin with an initial random
assignment. We put the [UNKNOWN] independently for
[UNKNOWN] and variable to the time and whether it starts of true or starts of
false. Then we get a budget of 2n^2 local moves
in an attempt transform this initial assignment into one that satisfies In
equities 2n^2 inner iterations we first check if the current assignment is
satisfying. Obviously if it is we're done.
So suppose that the current assignment is not a satisfying assignment then there is
at least 1 possibly many unsatisfied clauses, of them we take 1, arbitrarily.
Its a 2-SAT instance, so this cause involves 2 variables and if we flip the
value of either of those 2 variables we're going to make amends over this
clause. It will flip from one side Satisy to
satisfy. There's a tricky question of how you pick
which of the two variables you flip. Well, we take the easy way out, we just
pick one of the two uniformly [INAUDIBLE] at random.
If at the end of the day, after these 2n^2*LogN local moves, Papadimitriou's
algorithm has failed to find a satisfying assignment, it somewhat arrogantly
declares that therefore one must not exist.
What's clear about this algorithm is that is 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.
What's not at all obvious is the probability that Papadimitriou's
algorithm will find a satisfying assignment in the instances where at
least one such assignment exists. That analysis is the subject of this
video. And again what's remarkable and
surprising about this theorem is that if you think about the utmost natural
measure of progress for Papadimitriou's algorithm, mainly 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 fix the one clause, but you might screw up a bunch of others,
leaving you with an assignment that seems worse, in a sense that even fewer clauses
are satisfied than before. Nonetheless, if you define the right
measure of progress, you can argue, by a random waka analogy, that you are making
progress over time, resulting, eventually with a satisfying assignment.
Let's see the details. Each iteration of the outer 4 loop
represents a fresh opportunity to discover a satisfying assignment.
All of these iterations of the outer 4 loop are identical, they just used fresh
random coins. So let's just analyze for now the success
probability of a particular outer iteration.
We're assuming that this instance is satisfiable, so there's, there's at
least, perhaps many satisfying assignments.
Pick 1, an arbitrary one, I don't care which, call it A*.
Lets denote, by A sub t, the assignment that [UNKNOWN] Demetri's algorithm is
considering, after t iterations of the inner four-loop have completed.
So, A sub 0, that's the random initial assignment with which we begin, this
iteration of the outer four-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, its
a function of the random choices made by Papadimitriou algorithm.
Now the great idea in this analysis is to use the right progress measure rather
than 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 star.
Evidently, X sub T is an integer, it's 0 if A assigns every variable the opposite
of what A star does and it's equal to N if A and A star are exactly the same
assignment. Of course, if we ever get to the point
where x sub t=n, and a star is the same a s at, then at is itself a satisfying
assignment and we're good to go. The algorithm halts correctly.
Now we come to the key point in the analysis, now we're going to understand
the sense in which the algorithm on average makes progress.
So suppose we're 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 of I and X of J. For example, if it looks at the clause
not X of 3 or X of 7, then it's involving the variables X of 3.
And X of 7. So here's an easy observation.
Our current assignment A sub T is failing to satisfy this clause.
The reference satisfying assignment, A star, naturally is satisfying this
clause. Therefore A star must give a different
value to one of the 2 variables XI or XJ, than our assignment A sub T does.
It is also possible of course, that A star makes different assignments to both
of the variables, XI and XJ. All we know is that A star satisfies the
clause, whereas our assignment A sub T does not.
And the amazing part is just this simple observation is enough to imply that we're
going to make progress on average. Here's exactly what I mean.
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 in 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 star.
If both of our value assignments of these variables was the opposite of a star,
then whichever one we flip, we are going to share one more variable.
In agreement, with a star, than we did before.
That is, in our previous notation, X of T plus one, 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
star on exactly one of the two variables. XI and XJ.
So, for example maybe the current assignment agrees with A starred Xi but
disagrees with the reference assignment A star on XJ.
Now of course the algorithm has no idea what A star is, this arbitrary satisfying
assignment, so it has no idea which two of the variables XI or XJ it should
flipped, it just picked one of the two at.
Random. Now if we are lucky and we flip the value
of the variable on which a sub t at a* disagree and this is just like case one.
The flip causes the 2 assignments to agree on one more variable than they did
previously as a consequence X sub t+1 is going to.
Going to be one more than x of t. In the unlucky case we wind up flipping
the variable on which we agreed already with the reference assignment a star.
Then once we flip it we're going to disagree on yet another variable with the
reference assignment a star. So in that case x of t+1 is actually
going to be one less. Then x of t.
And now at this point I hope things are starting to look a little familiar
relative to our previous video about random [INAUDIBLE] in 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 1 or
down by 1. And with 50/50 probability each.
So the situation here with the x sub ts is clearly not identical to random locks
on non-negative integers, so the next quiz asks you to identify the differences
between the random process governing the x sub ts and your vanilla random lock on
the non-negative integers as studied in the previous video.
Video. So the answer is D.
If we think about 2 random processes, the 1st one is your straight forward random
walk in non-negative integers as discussed in the last video.
The 2nd random process is the evolution of these random variables, the X sub.
T's. The number of variables on which the
current assignment of Papnemeter's algorithm agrees with the reference
satisfying assignment a star, there are exactly 3 differences.
One we already pointed out. In the vanilla random walk in the line
ex, lets your position 0, if you're any bigger position its always 50-50 left or
right. In Papnemeters 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-star on both of the two variables.
Then it doesn't matter which of the 2 variables you pick, you're guaranteed to
agree with the reference assignment a-star on one more variable than before.
The second difference is that when we studied random walks, by definition, we
always started at position 0. That would correspond to this first
random variable x naught being equal to 0.
However, in general x naught will not be equal to 0.
In general it'll be strictly bigger than 0.
Why is that? Well, remember x naught is defined as The number of variables that
have the same value in the reference assignment A* and the initial random
assignment A0. So, the only way that X0 is going to be 0
is that you randomly chose an assignment where every variable had the opposite
value as what it is A* and that's very unlikely to happen.
Generally, you start with the random assignment, you're going to get lucky and
some of the values will be correct, will be the same as in A*, so X0 will
generally start bigger Than zero. 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 Parvati Metri's algorithm, what is
true, is if you ever get to Points that X of T equals N.
Then at that point the algorithm will terminate.
Why? Well, if X of T equals N, that means in the assignment A sub T every single
variable has exactly the same value as in the reference assignment A star.
Now, A stars are satisfying assignment and Papadimitriou's algorithm halts as
soon as it finds a satisfying assignment. So, if x of t=n, you've found a star,
you're good to go, you stop. However, the converse is not true.
Papadimitriou's algorithm might halt even though the current value of x of t is
less than. With an n.
Why is that ? or remember X of t measures your distance from this just 1 satisfying
assignment a*. 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 up on one of them before it
finds a*. So it holds the first time it finds the
satisfying assignment and that can happen before X of t equal N.
So where does this leave us? On the one hand it does seem to be a strong metaphor
between the distance between the assignment in Papademetris' algorithm and
this reference assignment A star 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 gotta be wondering is was that whole analysis last video useful.
Well, what's amazing and what allows us to transfer the random walk analysis over
to that of Apototometri's algorithm is that every single one of these three
discrepancies between the two random processes.
Only helps us, it only means the algorithm is going to terminate even
faster than we might have suspected from the random walk analysis.
So here's another way to think about it. Imagine I force you to run Padamitris
algorithm under an extremely unfortunate set of circumstances.
So first I give you a 2-SAT instance with just 1 satisfying assignment, so there's
a unique satisfying assignment A star, you're looking for a needle in a
haystack. There's no way you can get lucky by
halting early with a different satisfying assignment.
Secondly, I force you to begin from the worst possible initial assignment where
every variable's value initially is the wrong one, is flipped from what it should
be in a star. And finally imagine I further contrive
things so that whenever you pick unsatisfied clause to do a variable flip
I force you to pick a clause where one of the variables is set the same as an a*
and the other variable is set the opposite of a*.
Well for this kind of execution of [UNKNOWN] algorithm, the correspondence
between the evolution, the random variables, the x of t's and a random walk
on the non negative integers Is perfect. The two random processes are identical
under this worse case set of circumstances.
Therefore in the worst case circumstances, the probability of the
Papadimitriou algorithm fails to find a satisfying assignment, that is a star,
within 2n^2 steps is exactly the same as the probability that a random walk
beginning at 0 Fails to reach position n within 2n^2 steps and we analyse that
failure probability in the previous video, we proved its of most one half,
that is the success probability is at least one half.
Now if you look at any other circumstances other than the worst case
circumstances power meters algorithm is most likely to succeed.
So first of all it doesn't start as far away from a satisfying assignment.
Second of all this other satisfying assignments you might be able to find and
thirdly sometimes its guaranteed Need to make progress, as a point to have, as
opposed to only having a 50/50 chance. So the success probability under any
circumstances upon nature's algorithm is at least 50% in a given iteration of this
outer form. And now we're home free.
The probability that a given iteration of the outer for loop fails is at most 1/2,
the probability that each of the log base 2N iterations of the outer for loop fail
is then at most 1/2^Log base 2 of N, also known as 1/N, so the overall success
probability of the algorithm is at least 1-1/N as claimed.