Принцип Яо

В сложности вычислений теории принцип Яо (также называемый принципом минимакса Яо или леммой Яо ) — это способ доказать нижние границы в наихудшем случае производительности рандомизированных алгоритмов путем сравнения их с детерминированными (неслучайными) алгоритмами. Он утверждает, что для любого рандомизированного алгоритма существует распределение вероятностей на входных данных алгоритма, так что ожидаемая стоимость рандомизированного алгоритма на его входных данных в наихудшем случае по крайней мере так же велика, как стоимость лучшего детерминированного алгоритма на входных данных алгоритма. случайный вход из этого распределения. Таким образом, чтобы установить нижнюю границу производительности рандомизированных алгоритмов, достаточно найти подходящее распределение сложных входных данных и доказать, что ни один детерминированный алгоритм не может хорошо работать при таком распределении. Этот принцип назван в честь Эндрю Яо , который первым его предложил.

Принцип Яо можно интерпретировать в терминах теории игр через игру двух игроков с нулевой суммой , в которой один игрок, Алиса , выбирает детерминированный алгоритм, другой игрок, Боб, выбирает входные данные, а выигрыш представляет собой стоимость выбранного алгоритма. алгоритм на выбранном входе. Любой рандомизированный алгоритм R можно интерпретировать как рандомизированный выбор среди детерминированных алгоритмов и, следовательно, как смешанную стратегию для Алисы. Точно так же неслучайный алгоритм можно рассматривать как чистую стратегию для Алисы. Согласно фон Неймана минимаксной теореме , у Боба есть рандомизированная стратегия, которая работает как против R, так и против лучшей чистой стратегии, которую могла бы выбрать Алиса. Входные данные в худшем случае против стратегии Алисы стоили по крайней мере столько же, сколько случайно выбранные входные данные Боба в паре со стратегией Алисы, которые, в свою очередь, стоили по крайней мере столько же, сколько случайно выбранные входные данные Боба в паре с любой чистой стратегией.

Заявление

В приведенной ниже формулировке изложен принцип рандомизированных алгоритмов Лас-Вегаса , т. е. распределения по детерминированным алгоритмам, которые верны на всех входных данных, но имеют разные затраты. Этот принцип легко адаптировать к алгоритмам Монте-Карло , т. е. к распределениям по детерминированным алгоритмам, которые имеют ограниченные затраты, но могут быть неверными на некоторых входных данных.

Рассмотрим задачу над входными данными ${\mathcal {X}}$, и пусть ${\mathcal {A}}$ быть набором всех возможных детерминированных алгоритмов, которые правильно решают задачу.Для любого алгоритма $a\in {\mathcal {A}}$ и ввод $x\in {\mathcal {X}}$, позволять $c(a,x)\geq 0$ быть стоимостью алгоритма $a$ запускать на входе $x$.

Позволять $p$ быть распределением вероятностей по алгоритмам ${\mathcal {A}}$, и пусть $A$ обозначают случайный алгоритм, выбранный в соответствии с $p$. Позволять $q$ быть распределением вероятностей по входным параметрам ${\mathcal {X}}$, и пусть $X$ обозначают случайный вход, выбранный в соответствии с $q$. Затем,

${\underset {x\in {\mathcal {X}}}{\max }}\ \mathbf {E} [c(A,x)]\geq {\underset {a\in {\mathcal {A}}}{\min }}\ \mathbf {E} [c(a,X)].$

То есть ожидаемая стоимость рандомизированного алгоритма в наихудшем случае равна, по крайней мере, ожидаемой стоимости лучшего детерминированного алгоритма применительно к распределению входных данных. $q$.

Доказательство

Позволять $C={\underset {x\in {\mathcal {X}}}{\max }}\ \mathbf {E} [c(A,x)]$ и $D={\underset {a\in {\mathcal {A}}}{\min }}\ \mathbf {E} [c(a,X)]$. У нас есть

${\begin{aligned}C&=\sum _{x}q_{x}C\\&\geq \sum _{x}q_{x}\mathbf {E} [c(A,x)]\\&=\sum _{x}q_{x}\sum _{a}p_{a}c(a,x)\\&=\sum _{a}p_{a}\sum _{x}q_{x}c(a,x)\\&=\sum _{a}p_{a}\mathbf {E} [c(a,X)]\\&\geq \sum _{a}p_{a}D=D.\end{aligned}}$

Как упоминалось выше, эту теорему также можно рассматривать как весьма частный случай теоремы о минимаксе .

См. также

• Рандомизированные алгоритмы как игры с нулевой суммой

Ссылки

• Бородин, Аллан ; Эль-Янив, Ран (2005), «8.3 Принцип Яо: метод получения нижних границ» , Онлайн-вычисления и конкурентный анализ , Cambridge University Press, стр. 115–120, ISBN  9780521619462
• Яо, Эндрю (1977), «Вероятностные вычисления: к единой мере сложности», Труды 18-го симпозиума IEEE по основам информатики (FOCS) , стр. 222–227, doi : 10.1109/SFCS.1977.24

Внешние ссылки

• Фортнау, Лэнс (16 октября 2006 г.), «Любимые теоремы: принцип Яо» , Вычислительная сложность