Yao's principle

In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a>, Yao's principle (also called Yao's minimax principle or Yao's lemma) relates the performance of <a href="/facts/Randomized_algorithm/Fngl1zgk">randomized algorithms</a> to deterministic (non-random) algorithms. It states that, for certain classes of algorithms, and certain measures of the performance of the algorithms, the following two quantities are equal:

<ul><li>The optimal performance that can be obtained by a deterministic algorithm on a random input (its <a href="/facts/Average-case_complexity/6TqLIMMz">average-case complexity</a>), for a <a href="/facts/Probability_distribution/EpsKKVRu">probability distribution</a> on inputs chosen to be as hard as possible and for an algorithm chosen to work as well as possible against that distribution</li>
<li>The optimal performance that can be obtained by a random algorithm on a deterministic input (its expected complexity), for an algorithm chosen to have the best performance on its <a href="/facts/Worst_case_analysis/9ERhKtxB">worst case</a> inputs, and the worst case input to the algorithm</li></ul>
Yao's principle is often used to prove limitations on the performance of randomized algorithms, by finding a probability distribution on inputs that is difficult for deterministic algorithms, and inferring that randomized algorithms have the same limitation on their worst case performance.
This principle is named after <a href="/facts/Andrew_Yao/F5AHrY0e">Andrew Yao</a>, who first proposed it in a 1977 paper. It is closely related to the <a href="/facts/Minimax_theorem/PMFTLJf1">minimax theorem</a> in the theory of <a href="/facts/Zero-sum_game/ccouScgK">zero-sum games</a>, and to the <a href="/facts/Dual_linear_program/Qm3r26pm">duality theory of linear programs</a>.

Yao's principle open-in-new

Yao's principle