Введение

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

Заявление

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

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

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