無作為化アルゴリズムは、一連の決定論的アルゴリズムにわたる確率分布ですか？

Question

サイズnのインスタンスの有限セットと（合理的な）決定論的アルゴリズムのセットがフィニットされています。

は、一連の決定論的アルゴリズムにわたる確率分布と見なすことができますか？もしそうなら、なぜ？

Answer 1

ランダム変数 $ \ mathbf {r} $ にアクセスできるように、ランダム化されたアルゴリズムを考えることができます。 $ \ mathbf {r} $ の修正のために、決定論的アルゴリズムを得るため、このようにして、元のランダム化されたアルゴリズムを決定論的アルゴリズムの分布として表示することができます。

例として、MAX-3SATを解くためのランダム化アルゴリズムを検討してください。アルゴリズムはランダムな割り当てを選択します。 $ \ mathbf {r} $ で指定されたようにこの代入を考えることができます。特定の割り当ては決定論的アルゴリズムに対応し、元のランダム化アルゴリズムはこれらの決定論的アルゴリズムに対する単なる一様分布である。