Encyclopedia > Y > Yao's Principle
Yao's Principle
Andrew Yao proposed that to establish a lower bound on the expected worst-case cost of a randomized algorithm, evaluate the minimum cost of a deterministic algorithm on a probability distribution over the problem instances.
Information are taken from Wikipedia, the open encyclopedia, to which contribute many volunteers from around the whole world. Texts are available under the following conditions GNU Free Documentation License.
Encyklopedie (cz) Encyklopédia (sk) Enzyklopädie (de)