3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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$. $\endgroup$ – Anonymous Aug 6 '18 at 20:41
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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