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: The optimal performance that can be obtained by a deterministic algorithm on a random input (its average-case complexity), for a probability distribution on inputs chosen to be as hard as possible and for an algorithm chosen to work as well as possible against that distribution 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 worst case inputs, and the worst case input to the algorithm 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.
Formulation Yao's principle is formulated in terms of an arbitrary real valued cost measure of an algorithm on an input , 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 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 , which can be made finite in the same way. Then, each probability distribution over corresponds to a randomized algorithm that first makes a random choice from 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 of all probability distributions over . Finally, the formulation of Yao's principle involves the class of all probability distributions on inputs in , denoted as . Then, Yao's principle states that:
Here, is notation for the expected value, and means that is a random variable distributed according to . The left hand side of the formula gives the optimal performance that can be obtained by a deterministic algorithm on a random input (its average-case complexity), for a probability distribution on inputs that is as hard as possible and with being the algorithm that performs best against . The right hand side gives the optimal performance that can be obtained by a random algorithm on a deterministic input (its expected complexity), when has the best performance on its worst case inputs, and when is a worst case input to . The finiteness of and allows and 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 and for every randomized
That is, the best possible deterministic performance against distribution is a lower bound for the performance of each randomized algorithm against its worst-case input. This version of Yao's principle can be proven through the chain of inequalities
each of which can be shown using only linearity of expectation and the principle that for all distributions. By avoiding maximization and minimization over and , this version of Yao's principle can apply in some cases where or 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.
Applications and examples Time complexity When the cost 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.
Comparisons The time complexity of comparison-based sorting and selection algorithms is often studied using the number of comparisons between pairs of data elements as a proxy for the total time. When these problems are considered over a fixed set of elements, their inputs can be expressed as permutations and a deterministic algorithm can be expressed as a decision tree. In this way both the inputs and the algorithms form finite sets as Yao's principle requires. A symmetrization argument identifies the hardest input distributions: They are the random permutations, the distributions on distinct elements for which all permutations are equally likely. This is because, if any other distribution were hardest, averaging it with all permutations of the same hard distribution would be equally hard, and would produce the distribution for a random permutation. Yao's principle extends lower bounds for the average case number of comparisons made by deterministic algorithms, for random permutations, to the worst case analysis of randomized comparison algorithms.
An example given by Yao is the analysis of algorithms for finding the th largest of a given set of values, the selection problem. Subsequently, to Yao's work, Walter Cunto and Ian Munro showed that, for random permutations, any deterministic algorithm must perform at least expected comparisons. By Yao's principle, the same number of comparisons must be made by randomized algorithms on their worst-case input. The Floyd–Rivest algorithm comes within comparisons of this bound.
Evasiveness of graph properties Another of the original applications by Yao of his principle was to the evasiveness of graph properties, the number of tests of the adjacency of pairs of vertices needed to determine whether a graph has a given property, when the only access to the graph is through such tests. Richard M. Karp conjectured that every randomized algorithm for every nontrivial monotone graph property (a property that remains true for every subgraph of a graph with the property) requires a quadratic number of tests, but only weaker bounds have been proven.
As Yao stated, for graph properties that are true of the empty graph but false for some other graph on vertices with only a bounded number of edges, a randomized algorithm must probe a quadratic number of pairs of vertices. For instance, for the property of being a planar graph, because the 9-edge utility graph is non-planar. More precisely, Yao states that for these properties, at least tests are needed, for every , for a randomized algorithm to have probability at most of making a mistake. Yao also used this method to show that quadratically many queries are needed for the properties of containing a given tree or clique as a subgraph, of containing a perfect matching, and of containing a Hamiltonian cycle, for small enough constant error probabilities.
Black-box optimization In black-box optimization, the problem is to determine the minimum or maximum value of a function, from a given class of functions, accessible only through calls to the function on arguments from some finite domain. In this case, the cost to be optimized is the number of calls. Yao's principle has been described as "the only method available for proving lower bounds for all randomized search heuristics for selected classes of problems". Results that can be proven in this way include the following: For Boolean functions on -bit binary strings that test whether the input equals some fixed but unknown string, the optimal expected number of function calls needed to find the unknown string is . This can be achieved by a function that tests strings in a random order, and proved optimal by using Yao's principle on an input distribution that chooses a uniformly random function from this class. A unimodal function from -bit binary strings to real numbers is defined by the following property: For each input string , either is the unique maximum value of , or can be changed in a single bit to a string with a larger value. Thus, a local search that changes one bit at a time when this produces a larger value will always eventually find the maximum value. Such a search may take exponentially many steps, but nothing significantly better is possible. For any randomized algorithm that performs queries, some function in this class will cause the algorithm to have an exponentially small probability of finding the maximum.
Communication complexity In communication complexity, an algorithm describes a communication protocol between two or more parties, and its cost may be the number of bits or messages transmitted between the parties. In this case, Yao's principle describes an equality between the average-case complexity of deterministic communication protocols, on an input distribution that is the worst case for the problem, and the expected communication complexity of randomized protocols on their worst-case inputs.
An example described by Avi Wigderson (based on a paper by Manu Viola) is the communication complexity for two parties, each holding -bit input values, to determine which value is larger. For deterministic communication protocols, nothing better than bits of communication is possible, easily achieved by one party sending their whole input to the other. However, parties with a shared source of randomness and a fixed error probability can exchange 1-bit hash functions of prefixes of the input to perform a noisy binary search for the first position where their inputs differ, achieving bits of communication. This is within a constant factor of optimal, as can be shown via Yao's principle with an input distribution that chooses the position of the first difference uniformly at random, and then chooses random strings for the shared prefix up to that position and the rest of the inputs after that position.
Online algorithms Yao's principle has also been applied to the competitive ratio of online algorithms. An online algorithm must respond to a sequence of requests, without knowledge of future requests, incurring some cost or profit per request depending on its choices. The competitive ratio is the ratio of its cost or profit to the value that could be achieved by an offline algorithm with access to knowledge of all future requests, for a worst-case request sequence that causes this ratio to be as far from one as possible. Here, one must be careful to formulate the ratio with the algorithm's performance in the numerator and the optimal performance of an offline algorithm in the denominator, so that the cost measure can be formulated as an expected value rather than as the reciprocal of an expected value.