Принцип Яо - Yaos principle - Wikipedia

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

Принцип Яо можно интерпретировать в теоретическая игра условия, через двух игроков игра с нулевой суммой в котором один игрок, Алиса, выбирает детерминированный алгоритм, другой игрок, Боб, выбирает вход, а выплата - это стоимость выбранного алгоритма на выбранном входе. Любой рандомизированный алгоритм р может интерпретироваться как рандомизированный выбор среди детерминированных алгоритмов и, таким образом, как стратегия для Алисы. К фон Неймана теорема о минимаксе, У Боба есть рандомизированная стратегия, которая не хуже р как это происходит против лучшей чистой стратегии, которую может выбрать Алиса; то есть стратегия Боба определяет такое распределение входных данных, что ожидаемая стоимость р в этом распределении (и, следовательно, ожидаемая стоимость наихудшего случая р) не лучше, чем ожидаемая стоимость любого детерминированного алгоритма для того же распределения.

Заявление

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

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

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

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

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

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

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

${\displaystyle 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.}$

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

Рекомендации

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

внешняя ссылка

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