0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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$
    – Subhankar Ghosal
    Feb 13, 2021 at 1:08

0

Reset to default

Your Answer

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