# Consequence of having a randomised algorithm for graph colouring, which shows Yes and No with probability $1$ and $p(n) \sim_{n} 1$

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."

• 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).
• So can we take it further? graph coloring is in NP-complete. So does it not imply that $NP \subseteq co-RP$. Commented Apr 17, 2022 at 20:49
• @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$. Commented Apr 17, 2022 at 20:59
• OKK. So @Yuvai if graph coloring in coRP that implies $NP \subseteq coRP$. Am I getting correct? Commented Apr 18, 2022 at 11:34