Принцип Яо
В теории сложности вычислений принцип Яо или минимаксный принцип Яо гласит, что ожидаемое время работы вероятностного алгоритма в наихудшем случае не меньше, чем ожидаемое время работы на наихудшем распределении на входных данных детерминированного алгоритма, который лучше всего подходит для этого распределения. Таким образом, чтобы установить нижнюю границу производительности вероятностных алгоритмов, достаточно найти подходящее распределение трудных входов и доказать, что ни один детерминированный алгоритм не может хорошо работать против этого распределения. Этот принцип назван в честь Эндрю Яо, который первым предложил его.
Литература
- 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).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.