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:
“The force of truth that a statement imparts, then, its prominence among the hordes of recorded observations that I may optionally apply to my own life, depends, in addition to the sense that it is argumentatively defensible, on the sense that someone like me, and someone I like, whose voice is audible and who is at least notionally in the same room with me, does or can possibly hold it to be compellingly true.”
—Nicholson Baker (b. 1957)
“It is commonplace that a problem stated is well on its way to solution, for statement of the nature of a problem signifies that the underlying quality is being transformed into determinate distinctions of terms and relations or has become an object of articulate thought.”
—John Dewey (1859–1952)
“Most personal correspondence of today consists of letters the first half of which are given over to an indexed statement of why the writer hasn’t written before, followed by one paragraph of small talk, with the remainder devoted to reasons why it is imperative that the letter be brought to a close.”
—Robert Benchley (1889–1945)