1
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 n...