# Can we efficiently distinguish between P and BPP?

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$?

• $L_A$ is the language accepted by deterministic Turing machine $A$. $\langle A \rangle$ is the encoding of $A$ using some reasonable encoding, the details of encoding normally do not matter in problems like this. $D$ is a function and $D(\langle A \rangle)$ is the output of $D$ on $\langle A \rangle$. Think of $D$ as a diagonal function against $P$, given the description of a polynomial time Turing machine $A$, $D$ generates a string is accepted by $L$ iff it is not accepted by $A$. – Anonymous Aug 6 '18 at 20:41

## 1 Answer

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.

• Thank you for the answer, but I am really looking for a proof, not an analogy. – Anonymous Aug 6 '18 at 20:44
• @Anonymous Sure, that makes sense – Bjørn Kjos-Hanssen Aug 6 '18 at 21:43
• It's too long for a comment... – Bjørn Kjos-Hanssen Aug 12 '18 at 1:18