Can we efficiently distinguish between P and BPP?

Question

Let's say algorithm $D$ distinguishes $BPP$ from $P$ if there exists a language $L \in BPP$ such that for all $A \in PTM$, $$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A$$

Can we show this statement is false for all polynomial time algorithms $D$?

---

The question can be phrase in another way. $BPP \neq P$ iff there is a function $D$ such that for some language $L\in BPP$ and for all $A \in P$ we have $$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A$$

Most researchers seem to lean towards $P=BPP$, so we don't expect there is any such $D$.

Can we at least prove that there is no polynomial time computable function $D$ separating $P$ from $BPP$?

Answer 1

You defined that algorithm $D$ distinguishes $BPP$ from $P$ if there exists a language $L \in BPP$ such that for all $A \in PTM$, $$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \notin L_A.$$

Here as I understand it $L_A$ is the language accepted by $A$, $\langle A\rangle$ is a code for $A$, and $D$ takes such a code and outputs a string that may or may not be in $L$ or in $L_A$.

One particular way this could happen is if $D(\langle A)=\langle A\rangle$ for all $A$, or to write it more succinctly, $D(e)=e$ for all $e$. Instead of $L_A$ we may write $\phi_e$.

Then the condition is $$e\in L\leftrightarrow e\not\in\phi_e,$$ or, if we consider a set to be identified with its characteristic function, $$ L(e)\ne \phi_e(e).$$ This now starts to look like saying that $L$ is a diagonally non-computable (DNC) function as studied in computability theory. There, we have two facts:

1. There is no noncomputable oracle $A$ such that with positive probability, a random oracle $B$ can compute $A$; and
2. with probability 1, a random oracle $B$ can compute a DNC function.
3. with probability 1, a random oracle $B$ cannot compute a DNC function taking values in $\{0,1\}$.

Here (1) is analogous to BPP=P which we don't know whether holds. And (3) is analogous to the statement that, assuming BPP$\ne$P, a random oracle cannot produce a $D$ as you suggest.

To conclude, I don't have an answer to your question, but

by a loose analogy with computability theory it seems somewhat implausible that such a function $D$ should exist even if BPP$\ne$P.