On the mean evaluation of polynomially reducible Boolean functions
From MaRDI portal
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}). \]
Recommendations
- Approximate evaluations of characteristic polynomials of Boolean functions
- Computational bound on complexity of polynomial representations of Boolean functions
- scientific article; zbMATH DE number 3867065
- Complexity of Boolean functions in a class of canonical polarized polynomials
- On the multiplicative complexity of some Boolean functions
- Lower Bounds on Representing Boolean Functions as Polynomials in Z_m
- scientific article; zbMATH DE number 4179291
- Complexity of Boolean functions in the class of polarized polynomial forms
- Complexity of Boolean functions in the class of canonical polarized polynomials
- On the multiplicative complexity of Boolean functions
Cited in
(2)
This page was built for publication: On the mean evaluation of polynomially reducible Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5936693)
