Schwartz–Zippel lemma can solve the polynomial identity testing in expected poly-time. As far as I know, there is no deterministic poly-time algorithm for the problem, but we do not know if the problem is NP-hard or not, right? Is there any NP-hard problem that can be solved in expected poly-time using a randomized algorithm? What are the consequences if such a thing exists?


It is a common belief that P=BPP. This means that any randomized polynomial time algorithm can be derandomized. The idea of the proof is to use a deterministic pseudorandom number generator to supply the randomized algorithm random bits. Such a pseudorandom number generator exists, for example, if SAT takes exponential time to solve (roughly).

Polynomial identity testing is usually presented as a slightly different kind of problem (or rather as several different kinds of problems), but again the common belief is that one should be able to do it deterministically.

(As common beliefs go, some people disagree.)

  • $\begingroup$ Thanks Yuval, if I understood correctly, it means that polynomial identity testing might be solvable in deterministic polynomial time, even if $P\neq BPP$. $\endgroup$ – Helium Jan 12 '15 at 1:09
  • $\begingroup$ This is probably true, though there might be reductions to the contrary. $\endgroup$ – Yuval Filmus Jan 12 '15 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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