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

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

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

Заявление

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

Рассмотрим проблему с входами , и разреши - набор всех возможных детерминированных алгоритмов, которые правильно решают задачу. Для любого алгоритма и ввод , позволять быть стоимостью алгоритма запускать при вводе .

Позволять - распределение вероятностей по алгоритмам , и разреши обозначают случайный алгоритм, выбранный согласно . Позволять - распределение вероятностей по входам , и разреши обозначают случайный вход, выбранный в соответствии с . Потом,

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

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

Позволять и . У нас есть

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

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

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

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