
554 Kanellakis
sors is a potentially useful algorithm for the entire range of 1 up to m proces-
sors.
Randomization
can also play an important role, combined either with NC
or with optimal parallel algorithms. Randomized algorithms are like PRAM al-
gorithms, where each processor can at any step flip an unbiased coin and the
coin flips of different processors are independent. Without any assumptions on
the distribution of their inputs, randomized algorithms compute the correct
answer with overwhelming probability, e.g., Karp et al. [1985], Rabin [1980],
Schwartz [1980]. For example, the algorithm in Karp et al. [1985] is a ran-
domized poly logarithmi ...