В теории сложности вычислений , принцип Яо (также называемый принципом минимакса Яо или леммой Яо ) заявляет , что ожидаемая стоимость из рандомизированного алгоритма на наихудшем входе не лучше ожидаемой стоимости для наихудшего случая распределения вероятностей на входах детерминированный алгоритмкоторый лучше всего работает с этим распределением. Таким образом, чтобы установить нижнюю границу производительности рандомизированных алгоритмов, достаточно найти подходящее распределение сложных входных данных и доказать, что ни один детерминированный алгоритм не может хорошо работать с этим распределением. Этот принцип назван в честь Эндрю Яо , который первым его предложил.
Принцип Яо можно интерпретировать в терминах теории игр через игру двух игроков с нулевой суммой, в которой один игрок, Алиса , выбирает детерминированный алгоритм, другой игрок, Боб, выбирает вход, а выигрыш - это стоимость выбранных алгоритм на выбранном входе. Любой рандомизированный алгоритм R можно интерпретировать как рандомизированный выбор среди детерминированных алгоритмов и, таким образом, как стратегию для Алисы. Согласно теореме фон Неймана о минимаксе , у Боба есть рандомизированная стратегия, которая работает как минимум так же хорошо против R, как и против лучшей чистой стратегии, которую может выбрать Алиса; то есть стратегия Боба определяет такое распределение входных данных, что ожидаемая стоимость R в этом распределении (и, следовательно, ожидаемая стоимость R в наихудшем случае ) не лучше, чем ожидаемая стоимость любого отдельного детерминированного алгоритма по сравнению с тем же распределением.
Заявление
В приведенной ниже формулировке излагается принцип рандомизированных алгоритмов Лас-Вегаса , т. Е. Распределения по детерминированным алгоритмам, которые верны для всех входных данных, но имеют разные затраты. Этот принцип легко адаптировать к алгоритмам Монте-Карло , т. Е. К распределениям по детерминированным алгоритмам, которые имеют ограниченные затраты, но могут быть неправильными на некоторых входных данных.
Рассмотрим проблему с входами , и разреши набор всех возможных детерминированных алгоритмов, которые правильно решают проблему. Для любого алгоритма и ввод , позволять быть стоимостью алгоритма запускать при вводе .
Позволять - распределение вероятностей по алгоритмам , и разреши обозначают случайный алгоритм, выбранный согласно . Позволять - распределение вероятностей по входам , и разреши обозначают случайный вход, выбранный в соответствии с . Потом,
То есть ожидаемая стоимость рандомизированного алгоритма в наихудшем случае равна, по крайней мере, ожидаемой стоимости лучшего детерминированного алгоритма по отношению к распределению входных данных. .
Доказательство
Позволять а также . У нас есть
Как упоминалось выше, эту теорему также можно рассматривать как очень частный случай теоремы Минимакс .
Рекомендации
- Бородин, Аллан ; Эль-Янив, Ран (2005), «8.3 Принцип Яо: метод получения нижних оценок» , Онлайн-вычисления и конкурентный анализ , Cambridge University Press, стр. 115–120, ISBN 9780521619462
- Яо, Эндрю (1977), "Вероятностные вычисления: к единой мере сложности", Труды 18-го симпозиума IEEE по основам информатики (FOCS) , стр. 222–227, doi : 10.1109 / SFCS.1977.24
Внешние ссылки
- Фортноу, Ланс (16 октября 2006 г.), «Любимые теоремы: принцип Яо» , вычислительная сложность