Qualsiasi algoritmo randomizzato è una distribuzione della probabilità sul set di algoritmi deterministici?

Question

Se c'è un insieme finito di istanze di dimensioni n e il set di algoritmi deterministici (ragionevoli) è finita.

Qualsiasi algoritmo randomizzato può essere visto come una distribuzione della probabilità sul set di algoritmi deterministici?E se sì, perché?

Answer 1

Puoi pensare a un algoritmo randomizzato come avere accesso a una variabile casuale $ \ mathbf {r} $ , che informa le sue decisioni casuali.Per qualsiasi fissaggio di $ \ mathbf {r} $ , ottieni un algoritmo deterministico, e in questo modo è possibile visualizzare l'algoritmo randomizzato originale come distribuzione su algoritmi deterministici.

Ad esempio, considera l'algoritmo randomizzato per la risoluzione di max-3sat.L'algoritmo sceglie un incarico casuale.Puoi pensare a questo incarico come specificato da $ \ mathbf {r} $ .Qualsiasi incarico particolare corrisponde a un algoritmo deterministico e l'algoritmo randomizzato originale è solo la distribuzione uniforme su questi algoritmi deterministici.