# Does randomness make exponential difference?

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?

• Thanks Yuval, if I understood correctly, it means that polynomial identity testing might be solvable in deterministic polynomial time, even if $P\neq BPP$. – Helium Jan 12 '15 at 1:09