Show that for $n\to\infty$ there is such a boolean function $f:\{0,1\}^n\to \{0,1\}$ such that $n^3\le||f||\le2^{n-1}$ and with average complexity $T(f)=\theta(\frac{||f||}{log_2||f||})$. Help me solve this problem, I don't know where to start. If I come up with something, I'll add it here.
Asked
Active
Viewed 31 times
1
-
Could you define average complexity and $|f|$ please? – paulinho Dec 24 '20 at 15:18
-
@paulinho The weight of a Boolean function (that is, $||f||$) is the number of sets of values of input variables for which it takes the value 1. – gkndy Dec 24 '20 at 16:14
-
Thanks. And average complexity? – paulinho Dec 24 '20 at 17:52