10
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Worth noting that the input size is the number of bits needed to describe $f: \{0,1\}^n \to \{0,1\}$, which could be as large as $2^n$, in which case the brute-force algorithm is linear-time. $\endgroup$
    – usul
    May 29, 2023 at 14:31

1 Answer 1

22
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.