2
$\begingroup$

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$.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 28 at 18:48
  • $\begingroup$ Are you sure you mean ZPP rather than, say, RP? $\endgroup$ – Yuval Filmus Mar 28 at 18:59
  • $\begingroup$ @YuvalFilmus Sorry, it was a typo. Corrected. $\endgroup$ – Lecter Mar 28 at 19:00
  • 1
    $\begingroup$ 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}$. $\endgroup$ – Yuval Filmus Mar 28 at 19:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 28 at 19:36
3
+50
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.