# $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$$.

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

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

1. If $$M(G) = 1$$, output $$?$$.
2. 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 \}^*$$:

1. $$Pr[M(x) \in \{0,1\}] = 1$$,
2. if $$x \in L$$, then $$Pr[M(x) = 1] \geq 3/4$$,
3. 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 \}^*$$:

1. $$Pr[M(x) \in \{0,1,\text{?}\}] = 1$$ and $$Pr[M(x) = \text{?}] \leq 1/2$$,
2. if $$x \in L$$, then $$Pr[M(x) = 0] = 0$$,
3. if $$x \notin L$$, then $$Pr[M(x) = 1] = 0$$.
• If $\mathsf{k\text-COL \in P}$ then clearly $\mathsf{k\text{-}COL \in ZPP}$, so I don't really understand your question. Perhaps you should sketch your proof. Mar 28 '20 at 18:48
• Are you sure you mean ZPP rather than, say, RP? Mar 28 '20 at 18:59
• @YuvalFilmus Sorry, it was a typo. Corrected. Mar 28 '20 at 19:00
• Can you copy the exercise you are trying to answer? I'm not sure that $\mathsf{NP} \subseteq \mathsf{BPP}$ is known to imply $\mathsf{NP} \subseteq \mathsf{ZPP}$, but it is known to imply $\mathsf{NP} = \mathsf{RP}$. Mar 28 '20 at 19:05
• Your work doesn’t make much sense. Once you’ve determined whether your graph is $k$-colorable, you already know the answer. There’s nothing more to do. Mar 28 '20 at 19:36

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 &\subseteq NP \\ P \subseteq ZPP \subseteq coRP &\subseteq coNP \\ RP &\subseteq BPP \\ coRP &\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.