是否有任何隨機算法是確定性算法集上的概率分佈?


1

如果存在大小為n的有限實例集,並且(合理的)確定性算法集為finit。

任何隨機算法都可以看作是確定性算法集上的概率分佈嗎?如果可以,為什麼?

3

You can think of a randomized algorithm as having access to a random variable $\mathbf{r}$, which informs its random decisions. For any fixing of $\mathbf{r}$, you get a deterministic algorithm, and in this way you can view the original randomized algorithm as a distribution over deterministic algorithms.

As an example, consider the randomized algorithm for solving MAX-3SAT. The algorithm chooses a random assignment. You can think of this assignment as specified by $\mathbf{r}$. Any particular assignment corresponds to a deterministic algorithm, and the original randomized algorithm is just the uniform distribution over these deterministic algorithms.