As I’ve mentioned in the past, complexity theory isn’t really one of my favorite topics. As a professional computer scientist, knowing and loving complexity up to the level of NP-completeness
is practically a requirement. But once you start to get beyond P and NP, there are thousands of complexity classes that have been proposed for one reason or another, and really understanding all of them can get remarkably difficult, and what’s worse, can feel like an utterly pointless exercise,
particularly if the writer/teacher you’re learning from isn’t very good.
I’m not going to write a long series of posts on the more esoteric complexity classes. But there
are a few that are interesting, and might even have some relevance to actual practical problems in
selecting algorithms for a software system.
Today I’m going to talk about one of those practical classes, called BPP. BPP is the class of
problems that can be solved on a probabilistic machine in P-time with a bounded probability of
less than 1/2 of generating an incorrect result. (In general, we use 1/3 as the probability of failure,
but that’s just for convenience; you can pick any bound b you want from the range 0 < b
< 1/2, and you’ll wind up with the same set of problems in BPP.)
This is going to sound like a strange idea, but it’s actually quite useful. A probabilistic machine
is one which can, whenever it needs to during the execution of its program, flip a coin to select one
of two paths. If you can write a program which uses these random branches, and which will on average
generate correct results for better than 2 out of 3 executions, then the program is considered a
correct probabilistic solution to the problem, and the problem that it solves in in BPP.
Why is this useful?
Randomized algorithms are something we use in the real world. It’s rare that we can accurately
characterize the precise probability of generating a successful result, but BPP provides a model that
allows us to describe the capabilities of algorithms that use randomness. And even in cases where we
don’t really use randomness, we often approach exponential-time problems using heuristics – essentially
guesses about how to find a solution that work most of the time. To get some sense of what
benefit we can get from heuristics, we can model them as probabilistic branches – so again, BPP gives
us a way of exploring what the heuristics can do to the worst-case performance for a problem.
The most common kind of probabilistic algorithm is called a Monte Carlo algorithm. The
idea of a Monte Carlo algorithm is pretty simple. Imagine that you’ve got a barn with a target painted
on it, and your goal is to have a blind man put a bullet through the target. A Monte Carlo approach is
basically handing him a rapid-fire machine gun, pointing him in the right general direction, and having
him pull the trigger while moving the gun barrel back and forth until he’s fired a couple of hundred
shots. There’s a pretty good chance that at least one of those shots will wind up in the target. In
a Monte Carlo algorithm, you use some form of making a series of random guesses, each of which eliminates a group of possible solutions. After enough tries, whatever’s left is probably right.
The easiest example of this is one of the common algorithms for rapidly determining whether a
number is prime. Given an integer N which you think might be prime, randomly pick 10000 integers
between 2 and N1/2. For each one, check if it divides N evenly. If none of them divide it,
then there’s a high probability that it’s prime.
A slightly harder example of a probabilistic algorithm is one of the classic NP hard problems
is called the traveling salesman problem (TSP). In the TSP, you are a salesman who is given a route
including a set of N cities (nodes). You know the distance between any two cities in the list. The question is: what is the shortest path that allows you to visit all of the cities?
There’s a P-time probabilistic algorithm for the TSP based on a randomized heuristic which
generates an optimal solution with high probability. Basically, generate a random path. Then randomly pick a group of four nodes that are close together, and randomly rearrange them. If the
result is a shorter path, then that becomes the new path. If after some number *N* tries, the path doesn’t improve, then stop. (There are more details than that, but that’s the basic idea.) This algorithm can run in P-time, and generates optimal results with extremely high probability for problem sizes in the millions of nodes – problem sizes which would be absolutely intractable using
any conventional deterministic algorithm. It’s not guaranteed to generate a correct result; and in fact, I’ve
never seen an analysis that manages to specifically pin down its rate of success. But in practice,
its results are astonishingly good; I don’t think that for any test on hundreds on thousands of nodes where we know the correct answer that this algorithm didn’t find it.
(Note: The above explanation around the TSP was originally wrong. I managed to make
a major error in saying that the TSP was NP-complete. The TSP is not NP-complete;
it is NP-hard which is quite a lot worse. The TSP decision problem in NP-complete. The decision problem is: Given a path-length P, is there a path whose length is less than or equal to P? Just that decision part is NP-complete. Generating a path as a solution is quite a lot harder; well into EXP territory, even if it turns out that P=NP.)
There are also a couple of other interesting complexity classes that are related to BPP:
- RP: randomized polynomial time. This is a computational class for decision problems
– that is, problems which take an input, and return “Yes” or “No”. A problem is in RP if
there’s a probabilistic machine that always answers “No” if the correct answer
is “No”, and returns “Yes” more than 50% of the time if the correct answer is “Yes”. (What
this means is sort of the opposite of what it sounds like: if it answers “Yes”,
then it’s always right. If it answers “No”, then there’s some chance that it was
wrong.) We know that P ⊆ RP, and RP ⊆ BPP. (There was originally a type in this paragraph, where I wrote “A problem is in NP” where it correctly reads “A problem is NP”. Thanks to commenter Coin for the catch!)
- PP: probabilistic polynomial time. This is also a computational class for
decision problems. For a problem in PP, there is
a polynomial-time probabilistic algorithm where if the correct answer is “Yes”, the
algorithm will answer “Yes” more than half the time; if the correct answer
is “No”, it will answer “Yes” less than half the time. BPP ⊆ PP; PP
is a much weaker (in the sense of the strength of results required) class – an
algorithm in PP can end up arbitrarily close to being correct as often as
a coin-flip, no matter how many times you repeat the computation; whereas in BPP,
there is a probability bound, and by running the computation multiple times, you
can reduce the bound to get arbitrarily close to always being correct. In fact,
it turns out that NP ⊆ PP.