wikipedia読んだけどよくわからない。
複数の入力に対し、何らかのアルゴリズムに基づいて決定的な出力を行うという事だろうか。
a,b,cという入力から判断して0若しくは1を出力するみたいな。
但し、各入力がどのようなパラメータの手続きにより判断されるかはランダムみたいな。

いや、よくわからないけど。

何かの近似解の算出には使えるのかもしれない。
普通に解くと物凄い時間のかかる問題を高速に80%の確率で正答するとか。