Randomized Average Polynomial Time

Distributional problems with flat distributions may still be difficult on average. So one needs a way to identify hard-on-average problems with flat distributions. Since instances under flat distributions have uniformly small weights on instance size, searching for frequent enough instances of the target problem of a reduction to uniformly dominate frequent instances of the source problem is crucial. Venkatesan and Levin [VL88] made the suggestion of providing reductions with a good random source to help produce instances of the target problem with large enough probability. They showed that a graph edge coloring problem with a flat distribution is complete under a randomized reduction, by allowing algorithms to toss coins to determine the next moves. Blass and Gurevich [BG93] conducted a thorough study of such randomized reductions.

We assume that a randomized algorithm does not flip a coin unless the computation requires a random bit. For simplicity, coins are assumed to be unbiased. Randomized algorithms (to solve a problem) are allowed to make errors and produce incorrect outputs on some sequences of random bits. They can also run forever on some random (infinite) sequences. Let be a randomized algorithm. If on input halts and produces a correct output with being the random sequence it uses, then is called a good input for . Clearly, runs deterministically on . If on input runs deterministically, then is a good input, where denotes the empty string. Let be a set of good inputs for and . Let be an input distribution. If, for all with , is non-empty, then we call a good-input domain of (with respect to ). Clearly, no string in is a prefix of a different string in as, otherwise, the longer string cannot be in , as the algorithm stops before it can be generated. Let , which is called the rarity function of [BG93]. The smaller the value of the rarity function, the more good random sequences there are for the algorithm. If, for all , , then the randomized algorithm produces a correct output with probability 1. For our purposes, we need only to require that the value of be ``reasonable'' in the sense that is polynomial on average.

A good-input domain together with and a zero-size function for (i.e., ) is called a dilation in [Gur91a]. If the algorithm is for solving a search problem, the correctness of the output can be verified by evaluating the search predicate. For decision problems, if the randomized algorithm also provides a witness along with a yes/no answer, then the correctness of the answer can be verified by evaluating the witness (like search problems). If a witness is not provided, then one way to justify the correctness of the output is to make sure that the input is good. For instance, we may need to require that the good-input domain (with respect to ) be certifiable [BG93], meaning that for every input , whether is deterministically decidable in ap-time with respect to distribution . This notion of certifiability is stronger than the one used in [BG93].

By Definition 4.1, an ap-time randomized algorithm on input produces a correct output with probability , which could be small. While this may not seem satisfactory, Blass and Gurevich [BG93] showed that by iterating such an algorithm in an appropriate manner, a correct solution will be produced with probability 1 in average polynomial time. We assume that there is an efficient way to check whether an output of an iteration is correct as discussed above. Since a randomized algorithm may run a much longer time on inputs not in the good-input domain and it may not even halt on some bad inputs, a new iteration should start early without waiting for the previous one to stop. One way to carry it out is to use the ``round-robin'' method. Denote by the iteration of . At stage of , it independently carries out one step in the first, second, ..., and the th iterations of respectively in that order. stops as soon as one of the iterations stops with a correct output. So is a randomized algorithm whose sequence of random bits on input is the combination of random bits of each iteration in the round-robin fashion on the same input. This is equivalent to saying that flips a coin only when an iteration asks for a bit, and passes the random bit to that iteration. Several other iteration schemes have also been studied in [BG93][WB93b].

Proof Sketch. be a randomized algorithm that runs in time polynomial on -average. Let be a nonrare good-input domain. Let denote the set of all good inputs of . Then, for all , . Too see this, run on and let be the random sequence used by the th iteration and let be the random sequence used by . Since all these are independent, , where is the number of iterations. Let be the smallest with (namely, the th iteration is a ``successful'' one). Let be the time taken by on input with random sequence and let be the running time of . Then is bounded by a quadratic polynomial of . In the next two paragraphs, we will show that and are, in expectation, polynomially bounded. It follows that runs in time polynomial on -average. (The proof of the other direction is left to the reader.)

Let denote the expectation of the random variable . Let , for simplicity. Let . Then . Since is non-rare, there exists a such that

By Jensen's inequality, if is an increasing concave function on the interval then, for every random variable with values in , . Clearly, is an increasing concave function. Thus, .

By assumption, for some . In the following, is always assumed to be in , and is always assumed to be in . Note that, for all , . The event here is the intersection of the event and all events with . Since they are all independent, . Since is independent of the events with , . Since , . Thus,