In computational complexity theory, Yao's principle (also called Yao's minimax principle or Yao's lemma) relates the performance of randomized algorithms 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:

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 Andrew Yao, who first proposed it in a 1977 paper. It is closely related to the minimax theorem in the theory of zero-sum games, and to the duality theory of linear programs.

Yao's principle is formulated in terms of an arbitrary real valued cost measure ${\displaystyle c(A,x)}$ of an algorithm ${\displaystyle A}$ on an input ${\displaystyle x}$, such as its running time, for which one wishes to study the expected value over randomized algorithms and random inputs. The algorithms used in this cost measure are drawn from a finite set ${\displaystyle {\mathcal {A}}}$ of deterministic algorithms; a typical way to make a problem have only a finite set of algorithms is to restrict its inputs to a single size. The inputs, too, should be drawn from a finite set ${\displaystyle {\mathcal {X}}}$, which can be made finite in the same way. Then, each probability distribution over ${\displaystyle {\mathcal {A}}}$ corresponds to a randomized algorithm that first makes a random choice from ${\displaystyle {\mathcal {A}}}$ according to that distribution and then follows the chosen algorithm; in this way, the class of randomized algorithms for the same problem can be modeled as the class ${\displaystyle {\mathcal {R}}}$ of all probability distributions over ${\displaystyle {\mathcal {A}}}$. Finally, the formulation of Yao's principle involves the class of all probability distributions on inputs in ${\displaystyle {\mathcal {X}}}$, denoted as ${\displaystyle {\mathcal {D}}}$. Then, Yao's principle states that:

$${\displaystyle \max _{D\in {\mathcal {D}}}\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]=\min _{R\in {\mathcal {R}}}\max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].}$$

Here, ${\displaystyle \mathbb {E} }$ is notation for the expected value, and ${\displaystyle x\sim D}$ means that ${\displaystyle x}$ is a random variable distributed according to ${\displaystyle D}$. The left hand side of the formula gives the optimal performance that can be obtained by a deterministic algorithm ${\displaystyle A}$ on a random input ${\displaystyle x}$ (its average-case complexity), for a probability distribution ${\displaystyle D}$ on inputs that is as hard as possible and with ${\displaystyle A}$ being the algorithm that performs best against ${\displaystyle D}$. The right hand side gives the optimal performance that can be obtained by a random algorithm ${\displaystyle R}$ on a deterministic input ${\displaystyle x}$ (its expected complexity), when ${\displaystyle R}$ has the best performance on its worst case inputs, and when ${\displaystyle x}$ is a worst case input to ${\displaystyle R}$. The finiteness of ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {X}}}$ allows ${\displaystyle {\mathcal {D}}}$ and ${\displaystyle {\mathcal {R}}}$ to be interpreted as simplices of probability vectors, whose compactness implies that the minima and maxima in these formulas exist.

Another version of Yao's principle weakens it from an equality to an inequality, but at the same time generalizes it by relaxing the requirement that the algorithms and inputs come from a finite set. The direction of the inequality allows it to be used when a specific input distribution has been shown to be hard for deterministic algorithms, converting it into a lower bound on the cost of all randomized algorithms. In this version, for every input distribution ${\displaystyle D\in {\mathcal {D}}}$, and for every randomized algorithm ${\displaystyle R}$ in ${\displaystyle {\mathcal {R}}}$, $${\displaystyle \min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].}$$ That is, the best possible deterministic performance against distribution ${\displaystyle D}$ is a lower bound for the performance of each randomized algorithm ${\displaystyle R}$ against its worst-case input. This version of Yao's principle can be proven through the chain of inequalities $${\displaystyle \min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \mathbb {E} _{x\sim D}[c(R,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)],}$$ each of which can be shown using only linearity of expectation and the principle that ${\displaystyle \min \leq \mathbb {E} \leq \max }$ for all distributions. By avoiding maximization and minimization over ${\displaystyle {\mathcal {D}}}$ and ${\displaystyle {\mathcal {R}}}$, this version of Yao's principle can apply in some cases where ${\displaystyle {\mathcal {X}}}$ or ${\displaystyle {\mathcal {A}}}$ are not finite. Although this direction of inequality is the direction needed for proving lower bounds on randomized algorithms, the equality version of Yao's principle, when it is available, can also be useful in these proofs. The equality of the principle implies that there is no loss of generality in using the principle to prove lower bounds: whatever the actual best randomized algorithm might be, there is some input distribution through which a matching lower bound on its complexity can be proven.

When the cost ${\displaystyle c}$ denotes the running time of an algorithm, Yao's principle states that the best possible running time of a deterministic algorithm, on a hard input distribution, gives a lower bound for the expected time of any Las Vegas algorithm on its worst-case input. Here, a Las Vegas algorithm is a randomized algorithm whose runtime may vary, but for which the result is always correct. For example, this form of Yao's principle has been used to prove the optimality of certain Monte Carlo tree search algorithms for the exact evaluation of game trees.