Любой рандомизированный алгоритм распределения вероятности по набору детерминированных алгоритмов?

Question

Если есть конечный набор экземпляров размера N, а набор (разумных) детерминированных алгоритмов - это фин.

Может ли любой рандомизированный алгоритм рассматриваться как распределение вероятности по набору детерминированных алгоритмов?И если да, почему?

Answer 1

Вы можете подумать о рандомизированном алгоритме как имеющих доступ к случайной переменную $ \ mathbf {R} $ , который информирует его случайные решения.Для любой фиксации $ \ mathbf {r} $ вы получаете детерминированный алгоритм, а таким образом вы можете просмотреть исходный рандомизированный алгоритм в качестве распределения по детерминированным алгоритмам.

В качестве примера рассмотрим рандомизированный алгоритм для решения MAX-3SAT.Алгоритм выбирает случайное задание.Вы можете подумать об этом задании, как указано $ \ mathbf {r} $ .Любое конкретное задание соответствует детерминированному алгоритму, и исходный рандомизированный алгоритм является просто равномерным распределением этих детерминированных алгоритмов.