= Solution
Restrict the unknown <function> to the $n$ possibilities $f^{(i)}(x)=1$ if $x_i=1$, and $2$ otherwise. Each has exactly one <essential variable>, even if the allowed alphabet has more than two values. Every oracle answer in this restricted family is one <bit>.
A correct adaptive deterministic <algorithm> must distinguish all $n$ possibilities. A binary <decision tree> of depth $q$ has at most $2^q$ leaves, so $2^q\ge n$. Therefore \b[$q\ge\lceil\log_2n\rceil=\Omega(\log n)$]. Restricting the answer family is essential to the argument: unrestricted integer-valued answers need not have binary branching. Combined with part ii, this gives optimal logarithmic <query complexity> for fixed $d$.
Back to article page
