$k$-coloring in BPP, implies $k$-coloring in ZPP Consider the next problem:

$k$-COL: Given a graph $G=(V,E)$, does it have a valid $k$-coloring?

I need to prove that if $k$-COL is  in BPP, then it is also in ZPP. In other words, show that if there is a probabilistic polytime algorithm that decides whether a graph has a valid $k$-coloring or not with bounded error, then there is also a probabilistic polytime algorithm that does that with zero error.



My attempt

I've managed to prove it assuming that we are allowed to call an oracle that solves the above problem in polynomial time (see below).
But is there a way to show this without assuming $k$-COL $\in$ P?

Let $\mathcal{A}$ be a polynomial time machine with access to an oracle for $k$-COL.

Let $G$ be a graph and let $M$ be the BPP NTM that makes $k$-COL be in BPP. Let's define the following NTM $M'$:

If $G \in$ $k$-COL, execute $M$ on $G$.


If $M(G) = 1$, execute $\mathcal{A}$ on $G$. For sure, $\mathcal{A}(G)=1$.
If $M(G) = 0$, output $?$.


If $G \notin$ $k$-COL, execute $M$ on $G$.


If $M(G) = 1$, output $?$.
If $M(G) = 0$, execute $\mathcal{A}$ on $G$. For sure, $\mathcal{A}(G)=0$.


Definitions (for reference)

We define the class of languages Bounded-error Probabilistic Polynomial-time (BPP) as all $L \subseteq \{  0,1\}^*$ for which there exists a NTM $M$ and $c \geq 0$ such that $t_M=\mathcal{O}(n^c)$ and that for all $x \in \{ 0,1 \}^*$:


$Pr[M(x) \in \{0,1\}] = 1$,
if $x \in L$, then $Pr[M(x) = 1] \geq 3/4$,
if $x \notin L$, then $Pr[M(x) = 1] \leq 1/4$.


We define the class of languages Zero-error Probabilistic Polynomial-time (ZPP) as all $L \subseteq \{  0,1\}^*$ for which there exists a NTM $M$ and $c \geq 0$ such that $t_M=\mathcal{O}(n^c)$ and that for all $x \in \{ 0,1 \}^*$:


$Pr[M(x) \in \{0,1,\text{?}\}] = 1$ and $Pr[M(x) = \text{?}] \leq 1/2$,
if $x \in L$, then $Pr[M(x) = 0] = 0$,
if $x \notin L$, then $Pr[M(x) = 1] = 0$.
This statement is to my knowledge unknown. If this is an exercise, then it is likely an error: did they mean $RP$ instead of $ZPP$?

Since $k$-coloring is NP-complete, what you are asked to show is:


  If $NP \subseteq BPP$, then $NP = ZPP$.


First, let's review what is known: the basic inclusions are the following:
\begin{align*}
P \subseteq ZPP \subseteq RP &amp;\subseteq NP \\
P \subseteq ZPP \subseteq coRP &amp;\subseteq coNP \\
                          RP &amp;\subseteq BPP \\
                          coRP &amp;\subseteq BPP.
\end{align*}

That is, $P$ is contained in $ZPP = RP \cap coRP$, which is contained in $BPP$. Moreover, $RP$ is contained in $NP$ and $coRP$ is contained in $coNP$.
But we don't know how $NP$ and $coNP$ relate to $BPP$ (it is conjectured that $P = ZPP = BPP$, which implies that $NP$ and $coNP$ contain $BPP$).

Now, what happens if (as in your exercise) $NP \subseteq BPP$? It follows (and is a common exercise to show) that
$$
NP = RP.
$$

(see e.g. here).
That means that
$$
coRP = coNP \\
ZPP = NP \cap coNP \\
$$
So basically in this case, we have $P$, which contains $NP$ and $coNP$, and those are both contained in $BPP$ (which also equals the polynomial hierarchy $PH$).

But there is no reason to believe that this implies that $NP = coNP$, which is what you would need to then show that your $NP$-complete language, $k$-col, is in $ZPP = NP \cap coNP$. In particular, we can imagine that $BPP$ is equal to the second level of the polynomial hierarchy (you don't need to be familiar with this, but it's just some level that contains both $NP$ and $coNP$). That would imply that $NP$ is contained in $BPP$, but it doesn't mean that $NP$ and $coNP$ are equal.

TL;DR The statement you are trying to show appears to be unknown.