Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

Question

Recently, I came across the problem of figuring out whether a given binary function $f(x)$ is constant (0 for all values of $x$ or 1 for all values of $x$) or balanced (0 for half of values and 1 for the other half), for $x \leq N$.

Clearly, the complexity of a bounded error probabilistic algorithm is $O(1)$, because the probability of the function being constant if you get k random elements with the same value is less than $\frac{1}{2^k}$.

However, the deterministic algorithm is to check $f(x)$ for the possible values of $x$ until you find different values or $\frac{N}{2} + 1$ equal values. The time complexity for the worst case is $O(2^n)$, with $n$ being the number of bits of $N$, which is exponential.

To me it seems trivial that there is no better solution than this one, because you cannot be sure that two values inside a black box are different until you find them or get the maximum amount of equal numbers, so this problem is in $BPP$, but not in $P$.

What is wrong in my line of thought? Also, is this a "clue" that P is probably different from BPP?

Answer 1

It is true that if the function $f$ is given by an oracle, then a randomized algorithm is exponentially faster than any deterministic algorithm. With an oracle function, however, this is not a $BPP$ problem! It becomes a $BPP$ problem only if the function $f$ is given by a polynomial time algorithm, so that the whole task can be defined via a polynomial time Turing machine.

In that case, however, it is not clear that you indeed have to check exponentially many values in the deterministic case. You might be able to bypass it via capitalizing on knowing the special algorithm that computes $f$. (Note that knowing the algorithm is essential to make it a $BPP$ problem.)

Once you are in this setting, it might be possible to use the knowledge of the algorithm to devise a deterministic polynomial time solution. For example, by an appropriate pseudo random number generator you might be able to simulate the randomness well enough for the specific function $f$, so that the same solution is obtained as by the randomized algorithm. Whether this is indeed possible in every case is a major open question, it is the $P=?BPP$ problem.

Your line of thought can used, however, to prove that there is no universal deterministic pseudo random number generator, which works for every function $f$ in this setting.