Is it known that "For each problem in NP there is a randomized algorithm that solves it in polynomial time"? If not true then is there any proof of that. Or does it belongs to the unknown domain?

  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – D.W.
    Feb 12, 2021 at 19:52
  • 1
    $\begingroup$ Intuitively. $NP$ implies that, if a certificate is selected randomly, then a string from the language will be accepted with some probability $> 0$ (note that the probability can be exponentially small). For a randomized algorithm to work in polynomial time, we should have a version which accepts a string with probability $> \frac 1 {p(n)}$, where $p(n)$ is polynomial. So it's expected (but unknown) that such an algorithm doesn't exist. $\endgroup$
    – user114966
    Feb 12, 2021 at 21:28
  • $\begingroup$ @Dmitry does anyone framed this in literature as a conjecture which is still unsolved. At least then the corresponding researches could be traceable. I tried that but still not be able to find any answer to this question. $\endgroup$ Feb 13, 2021 at 1:08


Your Answer

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