Принцип Яо

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

Литература

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

Ссылки

• Fortnow, Lance Favorite theorems: Yao principle  (неопр.). Computational Complexity (16 октября 2006).