On randomized complexity of functions approximating the majority function (Q2746911)

The computational complexity of partial Boolean functions approximating the majority function by a modified RAM with a random number generator is considered. It is shown that there exist partial functions that approximate the majority function. The deterministic complexity of these functions exceeds their randomized complexity by the factor \(n\) (up to the order), where \(n\) is the number of variables of the Boolean functions under consideration.