If there is a finite set of Instances of size n and the set of (reasonable) deterministic algorithms is finit.
Can any randomized Algorithm be seen as a probability distribution over the set of deterministic Algorithms? And if yes, why?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Jul 13, 2020 at 12:17
-
$\begingroup$
For any fixing of r, you get a deterministic algorithm. The randomized algorithm may require an arbitrarily large number of random bits (depending on an input size). Therefore, each deterministic algorithm has to specify all these random bits in advance. How do you specify them so that your deterministic algorithm descriptions are finite? $\endgroup$– user114966Jul 13, 2020 at 13:24 -
2$\begingroup$ Good point. You have to make two assumptions. First, the algorithm always terminates, and so for any specific input size, there is an upper bound on the number of random bits. Second, the algorithm is allowed to be non-uniform, that is, to depend on the input size. $\endgroup$ Jul 13, 2020 at 14:01