Принцип Яо

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

Литература

• Yao, Andrew (1977), "Probabilistic computations: Toward a unified measure of complexity", Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS), сс. 222–227, DOI 10.1109/SFCS.1977.24 

Ссылки

• Fortnow, Lance Favorite theorems: Yao principle. Computational Complexity (October 16, 2006).