2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Dmitry Jul 13 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$ – Yuval Filmus Jul 13 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.