Computation of Boolean functions by randomized programs

AbstractThe average time of computing Boolean functions by straight-line programs with random number generators is studied. Reliable programs, which always compute the correct value of the function in question, and programs computing the desired value with some probability are considered. In both cases, it is shown that random number generators do not lead to a noticeable reduction in the average execution time for a large portion of the inputs. More exactly, for any Boolean function of n arguments whose circuit size is L, there exists a domain for which the ratio of L to the average time of computing the function by reliable programs does not exceed n. For randomized programs with a probability different from 1, this ratio may be only slightly greater than n