On the mean evaluation of polynomially reducible Boolean functions (Q5936693)

Let \(P(x)\) be the value of the program \(P\) on the set \(x\); \( T_P(x)\) is the working time of the program \(P\) on the set \(x\); \( T(P) = 2^{-n}\sum T_P(x) \) is the average working time of the program; \(T(f) = \min T(P) \) is the average time of computing the function \(f\). Let \(g\) and \(f\) be Boolean functions of \(n\) variables, \(g\) be polynomially reducible to \(f\) and \[ \lambda(n) = \max \frac{T(g)}{T(f)}. \] In the paper it is proved that \[ \lambda(n) = \Theta((2^n/n)^{1/2}). \]