# Is there any proof that says "For each problem in NP there is a randomized algorithm that solves that problem in expected polynomial time."

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?

• en.wikipedia.org/wiki/…
– D.W.
Feb 12, 2021 at 19:52
• 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.
– user114966
Feb 12, 2021 at 21:28
• @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. Feb 13, 2021 at 1:08