是任何随机算法在确定算法集合上的概率分布？

Question

如果有一个有限的大小的实例，并且该组（合理）确定性算法是有限的。

可以将任何随机算法视为多个确定性算法上的概率分布？如果是，为什么？

Answer 1

可以考虑一个随机算法，它可以访问随机变量 $ \ mathbf {r} $ ，它通知其随机决策。对于<跨度类=“math-container”> $ \ mathbf {r} $ ，您得到一个确定性算法，以这种方式，您可以将原始随机算法视为多种确定算法的分布。

作为示例，考虑用于求解MAX-3SAT的随机算法。该算法选择随机分配。您可以将此分配视为 $ \ mathbf {R} $ 。任何特定的赋值对应于确定性算法，并且原始随机算法只是这些确定性算法上的均匀分布。