词条 | Yao's principle |
释义 |
In computational complexity theory, Yao's principle or Yao's minimax principle states that the expected cost of a randomized algorithm on the worst case input, is no better than the expected cost, for a worst-case probability distribution on the inputs, of the deterministic 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 after Andrew 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's minimax 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. StatementLet 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 distribution 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 . ProofLet and . We have As mentioned above, this theorem can also be seen as a very special case of the Minimax theorem. References
| 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 = 1977 |doi= 10.1109/SFCS.1977.24 }} External links
2 : Computational complexity theory|Randomized algorithms |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。