
Title:
1802 Poking Around

Description:

So we have talked about using search trees, preprocessing,

and approximation to solve NP complete problems.

But there's one technique that we haven't yet talked about

and that is using randomness to solve challenging problems.

Now you know that so far in this course, I have always insisted

on finding guarantees for the performance of algorithms.

I wanted to have guarantees for the running time of the search trees.

I even wanted to have guarantees for approximation. So am I ready to give that up now?

Actually, I'm not, because even when we use randomness,

we can demand certain guarantees from our algorithms.

So, one way we could demand a guarantee from a random algorithm is,

that we say it produces the correct or best possible solution with a certain probability.

So best would be in the case of optimization problems

and correct, of course, in the case of decision problems.

And so, we'll also write this down for decision problems

and finally we could also say that the algorithm has a running time that is random,

and we want the running time to be polynomial with a certain probability

and of course in this case here, we would be demanding that the solution is always

the best possible solution or the correct solution.

Well, actually we could also have combinations of these,

but then the algorithm becomes rather weak in my mind

and actually I'm not aware of any example where I have seen this before.

Now, some of these approaches have special names

and this one here is known as a Monte Carlo algorithm,

and this one here is known as a Las Vegas approach.

Don't ask me what that says about casinos in

Europe versus casinos in America because I have no clue.

Now the two approaches, Monte Carlo and Las Vegas are actually related to each other,

and if you think about it for a little while, I think you can figure that out yourself.

So my question for you is how are Monte Carlo algorithms

and Las Vegas algorithms related to each other, and I'll give you three choices here.

Is it that any Las Vegas algorithm can be turned into a Monte Carlo algorithm?

So any algorithm over here can be turned into an algorithm like this.

Is it the other way around, that any Monte Carlo algorithm can be turned into a Las Vegas algorithm?

Or is it even that the two approaches are, roughly speaking, of course, more or less the same.