Qualquer algoritmo randomizado é uma distribuição de probabilidade sobre o conjunto de algoritmos determinísticos?

Question

Se houver um conjunto finito de instâncias de tamanho N e o conjunto de algoritmos determinísticos (razoáveis) é finit.

Qualquer algoritmo randomizado pode ser visto como uma distribuição de probabilidade sobre o conjunto de algoritmos determinísticos?E se sim, por quê?

Answer 1

Você pode pensar em um algoritmo randomizado como tendo acesso a uma variável aleatória $ \ mathbf {r} $ , que informa suas decisões aleatórias.Para qualquer fixação de $ \ mathbf {r} $ , você obtém um algoritmo determinístico, e desta forma você pode ver o algoritmo randomizado original como uma distribuição sobre algoritmos determinísticos.

Como exemplo, considere o algoritmo randomizado para resolver o max-3SAT.O algoritmo escolhe uma tarefa aleatória.Você pode pensar nessa tarefa, conforme especificado por $ \ mathbf {r} $ .Qualquer determinada atribuição corresponde a um algoritmo determinista, e o algoritmo randomizado original é apenas a distribuição uniforme sobre esses algoritmos determinísticos.