<p>It is true that if the function <span class="math-container">$f$</span> 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 <span class="math-container">$BPP$</span> problem! It becomes a <span class="math-container">$BPP$</span> problem only if the function <span class="math-container">$f$</span> is given by a polynomial time algorithm, so that the whole task can be defined via a polynomial time Turing machine.</p>
<p>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 <span class="math-container">$f$</span>. (Note that  knowing the algorithm is essential to make it a <span class="math-container">$BPP$</span> problem.)</p>
<p>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 <span class="math-container">$f$</span>, 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 <span class="math-container">$P=?BPP$</span> problem.</p>
<p>Your line of thought can used, however, to prove that there is no <strong>universal</strong> deterministic pseudo random number generator, which works for <em>every</em> function <span class="math-container">$f$</span>  in this setting.</p>

CC BY-SA 4.0
2023-05-27T04:18:44.037Z
2023-05-27T04:18:44.037Z
Andras Farago
<p>Recently, I came across the problem of figuring out whether a given binary function <span class="math-container">$f(x)$</span> is constant (0 for all values of <span class="math-container">$x$</span> or 1 for all values of <span class="math-container">$x$</span>) or balanced (0 for half of values and 1 for the other half), for <span class="math-container">$x \leq N$</span>.</p>
<p>Clearly, the complexity of a bounded error probabilistic algorithm is <span class="math-container">$O(1)$</span>, because the probability of the function being constant if you get k random elements with the same value is less than <span class="math-container">$\frac{1}{2^k}$</span>.</p>
<p>However, the deterministic algorithm is to check <span class="math-container">$f(x)$</span> for the possible values of <span class="math-container">$x$</span> until you find different values or <span class="math-container">$\frac{N}{2} + 1$</span> equal values. The time complexity for the worst case is <span class="math-container">$O(2^n)$</span>, with <span class="math-container">$n$</span> being the number of bits of <span class="math-container">$N$</span>, which is exponential.</p>
<p>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 <span class="math-container">$BPP$</span>, but not in <span class="math-container">$P$</span>.</p>
<p>What is wrong in my line of thought? Also, is this a &quot;clue&quot; that P is probably different from BPP?</p>

CC BY-SA 4.0
2023-05-29T14:31:31.577Z
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.
usul
<cc.complexity-theory><complexity-classes>
Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?
Thiago
# Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

(Asked by: username_0 on 2023-05-26)

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?

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2023-05-27. Score: 22 | Accepted answer

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.


---

