  Stochastic algorithms are among the best for solving computationally hard
search and reasoning problems. The runtime of such procedures is characterized
by a random variable. Different algorithms give rise to different probability
distributions. One can take advantage of such differences by combining several
algorithms into a portfolio, and running them in parallel or interleaving them
on a single processor. We provide a detailed evaluation of the portfolio
approach on distributions of hard combinatorial search problems. We show under
what conditions the protfolio approach can have a dramatic computational
advantage over the best traditional methods.
