Войти
В теории сложности вычислений, принцип Яо (также называемый принципом минимакса Яо или леммой Яо) заявляет, что ожидаемая стоимость из рандомизированного алгоритма на наихудшем входе не лучше ожидаемой стоимости для наихудшего случая распределения вероятностей на входах детерминированный алгоритм, который выполняет лучше от этого распределения. Таким образом, чтобы установить нижнюю границу производительности рандомизированных алгоритмов, достаточно найти соответствующее распределение сложных входных данных и доказать, что ни один детерминированный алгоритм не может хорошо работать с этим распределением. Этот принцип назван в честь Эндрю Яо, который первым его предложил.
Принцип Яо может быть интерпретирован в терминах теории игр через игру с нулевой суммой для двух игроков, в которой один игрок, Алиса, выбирает детерминированный алгоритм, другой игрок, Боб, выбирает вход, а выигрыш - это стоимость выбранного алгоритм на выбранном входе. Любой рандомизированный алгоритм R можно интерпретировать как рандомизированный выбор среди детерминированных алгоритмов и, таким образом, как стратегию для Алисы. Согласно теореме фон Неймана о минимаксе, у Боба есть рандомизированная стратегия, которая работает как минимум так же хорошо против R, как и против лучшей чистой стратегии, которую может выбрать Алиса; то есть стратегия Боба определяет такое распределение на входах, что ожидаемая стоимость R в этом распределении (и, следовательно, ожидаемая стоимость R в наихудшем случае) не лучше, чем ожидаемая стоимость любого детерминированного алгоритма для того же распределения.
В приведенной ниже формулировке излагается принцип рандомизированных алгоритмов Лас-Вегаса, т. Е. Распределения по детерминированным алгоритмам, которые верны на всех входных данных, но имеют разные затраты. Этот принцип легко адаптировать к алгоритмам Монте-Карло, т. Е. К распределениям по детерминированным алгоритмам, которые имеют ограниченные затраты, но могут быть неправильными на некоторых входных данных.
Рассмотрим проблему по входам, и пусть будет набор всех возможных детерминированных алгоритмов, которые правильно решают проблему. Для любого алгоритма и ввода позвольте быть стоимостью выполнения алгоритма при вводе.
Позвольте быть распределением вероятностей по алгоритмам, и пусть обозначить случайный алгоритм, выбранный согласно. Позвольте быть распределением вероятностей по входам, и пусть обозначить случайный вход, выбранный согласно. Потом,
То есть ожидаемая стоимость рандомизированного алгоритма в наихудшем случае - это, по крайней мере, ожидаемая стоимость лучшего детерминированного алгоритма по отношению к распределению входных данных.
Пусть и. У нас есть
Как упоминалось выше, эту теорему также можно рассматривать как очень частный случай теоремы Минимакс.
![{\ Displaystyle {\ underset {x \ in {\ mathcal {X}}} {\ max}} \ \ mathbf {E} [c (A, x)] \ geq {\ underset {a \ in {\ mathcal { A}}} {\ min}} \ \ mathbf {E} [c (a, X)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a62477a26a957ebebe1df19662d1b1e6716a1c9)
![{\ displaystyle C = {\ underset {x \ in {\ mathcal {X}}} {\ max}} \ \ mathbf {E} [c (A, x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/331a2baee308357e357f235a8fda94849afb67d3)
![{\ displaystyle D = {\ underset {a \ in {\ mathcal {A}}} {\ min}} \ \ mathbf {E} [c (a, X)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a026426ebdec106d7c0d84d6f3ef12502b220fc)
![{\ displaystyle {\ begin {align} C amp; = \ sum _ {x} q_ {x} C \\ amp; \ geq \ sum _ {x} q_ {x} \ mathbf {E} [c (A, x)] \\ amp; = \ sum _ {x} q_ {x} \ sum _ {a} p_ {a} c (a, x) \\ amp; = \ sum _ {a} p_ {a} \ sum _ {x} q_ {x} c (a, x) \\ amp; = \ sum _ {a} p_ {a} \ mathbf {E} [c (a, X)] \\ amp; \ geq \ sum _ {a} p_ { a} D = D. \ end {выравнивается}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d4c33ece53c235a13414a2c20c61c3584392e16d)