¿Algún algoritmo aleatorizado es una distribución de probabilidad sobre el conjunto de algoritmos deterministas?

Question

Si hay un conjunto finito de instancias de tamaño N y el conjunto de algoritmos deterministas (razonables) es FINIT.

¿Se puede ver algún algoritmo aleatorio como una distribución de probabilidad a través del conjunto de algoritmos deterministas?Y en caso afirmativo, ¿por qué?

Answer 1

Puede pensar en un algoritmo aleatorio como tener acceso a una variable aleatoria $ \ mathbf {r} $ , que informa sus decisiones aleatorias.Para cualquier fijación de $ \ mathbf {r} $ , obtiene un algoritmo determinista, y de esta manera puede ver el algoritmo aleatorizado original como una distribución sobre algoritmos deterministas.

Como ejemplo, considere el algoritmo aleatorio para resolver MAX-3SAT.El algoritmo elige una asignación aleatoria.Puede pensar en esta tarea según lo especificado por $ \ mathbf {r} $ .Cualquier asignación en particular corresponde a un algoritmo determinista, y el algoritmo aleatorizado original es solo la distribución uniforme sobre estos algoritmos deterministas.