Does randomness make exponential difference?
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.)