Suppose we have a randomized algorithm that takes a graph G and color k as inputs and provides yes if the graph is k-colorable and no with probability $p(n)$ if it's not k-colorable, where $n$ is the number of vertices. What is the consequence if someone comes with a proof that $\displaystyle \lim_{n \rightarrow \infty} p(n) = 1$.

Does it imply that graph coloring in BPP or ZPP?

N.B. I am familiar with randomized algorithms, NP, NP-completeness, and polynomial reductions as they were covered in Algorithms, Automata, and Languages. However, I didn't go too deep into complexity theory. In my understanding answer to the question is "if its true then graph coloring is in BPP."


1 Answer 1


The complexity class RP consists of problems which have a randomized algorithm, running in polynomial time, with the following properties:

  • If the answer is No, the algorithm always answers No.
  • If the answer is Yes, the algorithm answers Yes with probability at least $1/2$ (or at least $1/\mathit{poly}(n)$, or at least $1-1/\exp(\mathit{poly}(n))$ — the resulting class is the same).

You have a similar promise with Yes and No reversed, so the complexity class is coRP.

  • $\begingroup$ So can we take it further? graph coloring is in NP-complete. So does it not imply that $NP \subseteq co-RP$. $\endgroup$ Commented Apr 17, 2022 at 20:49
  • $\begingroup$ @Yuvai A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that 1. M runs for polynomial time on all inputs 2. For all x in L, M outputs 1 with probability greater than or equal to 2/3 [which is in this case 1] 3 . For all x not in L, M outputs 1 with probability less than or equal to 1/3. [here for all x probability is not < 1/3 but it is $\sim_{n} 1$. $\endgroup$ Commented Apr 17, 2022 at 20:59
  • $\begingroup$ So my basic question is, for finite instances does the probability of false-negative matters or the asymptotic probability of false-negative we have to consider? $\endgroup$ Commented Apr 17, 2022 at 21:05
  • $\begingroup$ Since the probability can be boosted as I indicate in my answer, it doesn’t matter as long as it is in the range indicated in my answer. $\endgroup$ Commented Apr 18, 2022 at 3:33
  • $\begingroup$ OKK. So @Yuvai if graph coloring in coRP that implies $NP \subseteq coRP$. Am I getting correct? $\endgroup$ Commented Apr 18, 2022 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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