<p>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.$$</p>

<p>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$.</p>

<p>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$.</p>

<p>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:</p>

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

<p>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.</p>

<p>To conclude, I don't have an answer to your question, but</p>

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

CC BY-SA 4.0
2018-08-06T20:44:53.400Z
Thank you for the answer, but I am really looking for a proof, not an analogy.
Anonymous
CC BY-SA 4.0
2018-08-06T21:43:48.790Z
@Anonymous Sure, that makes sense
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-08-12T01:18:01.647Z
It's too long for a comment...
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-08-06T20:40:09.977Z
2018-08-06T21:43:22.600Z
2018-08-06T21:43:22.600Z
Bjørn Kjos-Hanssen
<p>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$$</p>

<p>Can we show this statement is false for all polynomial time algorithms $D$?</p>

<hr>

<p>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$$</p>

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

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

CC BY-SA 4.0
2018-08-06T20:41:44.573Z
$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
<cc.complexity-theory><separation><probabilistic-computation>
Can we efficiently distinguish between P and BPP?
Anonymous
# Can we efficiently distinguish between P and BPP?

(Asked by: username_0 on 2018-08-05)

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

**Tags:** cc.complexity-theory, separation, probabilistic-computation

> **Comments:**
> **username_0**: $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$.  

---

## 1 answers

### Answer by username_1 on 2018-08-06. Score: 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.

> **Comments:**
> **username_0**: Thank you for the answer, but I am really looking for a proof, not an analogy.  
> **username_1**: @username_0 Sure, that makes sense  
> **username_1**: It's too long for a comment...  

---

