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.