So in the last quiz you have seen that it's not very likely
that we can find a randomized algorithm for an np complete problem
that in polynomial time will deliver us the right answer with a fixed probability
to be honest, we currently don't know if such an algorithm is possible or impossible
but many believe that it is highly unlikely
and so far no such algorithm has been discovered
it seems that sometimes, however, if we either cross this one here off our list or this one here off our list
and you'll soon see that it doesn't really matter what we cross off our list
but if we kind of reduce the number of wishes that we have
it seems that sometimes we can use randomness
to at least improve the running time of exponential time algorithms
so just as you've seen, when we optimize search trees
it's sometimes also possible to improve the running time of exponential time algorithms
or the base of the exponent using randomness
now the question is could we use randomness to help Alice solve vertex cover
or help Bob solve his clique problem, or Carol her independent set problem, or Dave his shortest tour problem
at least when we say that we do not have this requirement here
and the answer unfortunately is - we don't know
we don't know if there are good randomized algorithms
to solve vertex cover, or clique, or independent set, or shortest tour
at least not if we're demanding guarantees
so there are randomized algorithms that will look through a random number of solutions
and these are also used in practice, but again they do not offer any guarantees
there's one problem, however, that is MP complete where I can give you a randomized algorithm
that's at least better than the best known deterministic algorithm. And that problem is 3-SAT
As I hope you will remember, the 3-SAT problem had as an input a boolean formula with n variables
and the boolean formula has a special property because
it's 3-SAT, namely that each clause has exactly 3 variables
And the output I'm looking for is, an answer to the question
If this boolean formula, with n variables, where each clause has exactly 3 variables, has a satisfying assignment
So how can you use randomness to solve this problem?
Well there's a very simple, and in my mind very elegant, algorithm
that in 1999 was proposed by Uva Sherning to solve a 3-SAT instance with n variables
So this is the algorithm and as you can see it's really quite simple
So you start out by picking a random 0 - 1 assignment for the variables
and then you go into a loop that iterates 3n times, where n is the number of variables
and what you do each time in the loop
you take one of the clauses that is not satisfied and then you randomly flip one of the variables of that clause
So what does this randomly flipping mean?
You start out with a clause and we already know that this clause will have only 3 variables
because we're dealing with 3-SAT
Now you randomly pick one of those variables, say we randomly pick the 2nd one, and then you just flip its value
meaning, if it was assigned to true you now assign it to false, or vice versa
if it was assigned to false, now you set it to true
and since it's a random process we don't know which variable we're going to pick
So instead of this one here, we might have also picked this one here, and of course this one here
And what happens is by this flipping, you satisfy this clause, but of course other clauses might become unsatisfied
Now if we run this algorithm here once, what are the chances that it will succeed and find a satisfying assignment
provided that the initial boolean formula does indeed have a satisfying assignment
if it doesn't have a satisfying assignment, the algorithm can't find it
but let's assume that it has one
then the success of this algorithm will depend on two things
the first one is: how far the initial assignment is off the satisfying assignment
or, in other words, picking this random 0 - 1 assignment to the variables, how many variables did we get right?
and by right I mean we set them to the same value that they would have in a satisfying assignment
and the second one is, are these random choices that we make here, by flipping the variables, successful
So if we are somewhere near a satisfying assignment, and by chance the algorithm makes the right choices
then we would find a satisfying assignment
provided –but we made that assumption– that the boolean formula here actually has a satisfying assignment
But let's look at those two success factors a little more closely