- Yao's principle
Yaos principle states that the expected cost of any
randomized algorithm for solving a given problem, on theworst case input for that algorithm, can be no better than the expected cost, for a worst-case randomprobability distribution on the inputs, of thedeterministic algorithm that performs best against that distribution. Thus, to establish a lower bound on the performance of randomized algorithms, it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm can perform well against that distribution. This principle is named afterAndrew Yao , who first proposed it.Yao's principle may be interpreted in game theoretic terms, via a two-player
zero sum game in which one player, Alice, selects a deterministic algorithm, the other player, Bob, selects an input, and the payoff is the cost of the selected algorithm on the selected input. Any randomized algorithm "R" may be interpreted as a randomized choice among deterministic algorithms, and thus as a strategy for Alice. By von Neumann'sminimax theorem , Bob has a randomized strategy that performs at least as well against "R" as it does against the best pure strategy Alice might choose; that is, Bob's strategy defines a distribution on the inputs such that the expected cost of "R" on that distribution (and therefore also the worst case expected cost of "R") is no better than the expected cost of any single deterministic algorithm against the same distribution.References
*citation
last = Yao | first = Andrew | authorlink = Andrew Yao
contribution = Probabilistic computations: Toward a unified measure of complexity
title = Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS)
pages = 222–227 | year = 1977External links
* [http://weblog.fortnow.com/2006/10/favorite-theorems-yao-principle.html Favorite theorems: Yao principle] , Lance Fortnow, October 16, 2006.
Wikimedia Foundation. 2010.