Statement
Let us state the principle for Las Vegas randomized algorithms, i.e., distributions over deterministic algorithms that are correct on every input but have varying costs. It is straightforward to adapt the principle to Monte Carlo algorithms, i.e., distributions over deterministic algorithms that have bounded costs but can be incorrect on some inputs.
Consider a problem over the inputs, and let be the set of all possible deterministic algorithms that correctly solve the problem. For any algorithm and input, let be the cost of algorithm run on input .
Let be a probability distributions over the algorithms, and let denote a random algorithm chosen according to . Let be a probability distribution over the inputs, and let denote a random input chosen according to . Then,
- ,
i.e., the worst-case expected cost of the randomized algorithm is at least the cost of the best deterministic algorithm against input distribution .
Read more about this topic: Yao's Principle
Famous quotes containing the word statement:
“He has the common feeling of his profession. He enjoys a statement twice as much if it appears in fine print, and anything that turns up in a footnote ... takes on the character of divine revelation.”
—Margaret Halsey (b. 1910)
“Children should know there are limits to family finances or they will confuse “we can’t afford that” with “they don’t want me to have it.” The first statement is a realistic and objective assessment of a situation, while the other carries an emotional message.”
—Jean Ross Peterson (20th century)
“The parent is the strongest statement that the child hears regarding what it means to be alive and real. More than what we say or do, the way we are expresses what we think it means to be alive. So the articulate parent is less a telling than a listening individual.”
—Polly Berrien Berends (20th century)