There are several kinds of nondeterminism. In the case of nondeterministic complexity classes like NP, it's angelic nondeterminism: whenever the algorithm makes

There are several kinds of nondeterminism. In the case of nondeterministic complexity classes like NP, it's angelic nondeterminism: whenever the algorithm makes a non-deterministic choice, the machine obeys an oracle that will guide it to an accept state if there is any such choice. (I prefer the certifier view of NP, but that doesn't really explain the N in NP.) Nondeterministic complexity classes have little to do with randomness, and I think it's clear that always guessing right would be a good mutation to have ;) There are randomised complexity classes, which are germane to the discussion. Some classical ones are RP, ZPP and BPP (and RP's negative twin, co-RP). They are all variants of Polynomial-time with access to random bits. - RP captures Las Vegas algorithms (if the algorithm returns NO, the string is definitely rejected; otherwise, we may have a false positive with a probability bounded away from 0). - ZPP is the intersection of RP and co-RP: there is no error when the machine finally terminate, but only the expected running time is polynomial. - BPP captures Monte Carlo algorithms: the machine always terminates in polynomial time and is correct more often than not. However, any result (accept or reject) can be spurious. None of these complexity classes are known to be equivalent to P, although there's a strong feeling that BPP = P. In practice, any implementation is likely backed by a quick PRNG with a couple thousand bits of state at most, so it's not clear what separating ZPP and P would mean ;) If we visit more exotic complexity classes, we get some interesting insight in the relationship between P, NP and randomness. Probabilistically checkable proofs define families of proof systems. A PCP(r(n), q(n)) verifier accepts an input string and a specially constructed certificate (e.g., a proof witness that this SAT instance is satisfiable), and confirms that the certificate is valid in polynomial time, by using at most r(n) random bits and reading q(n) bits of the certificate. The verifier has to run in polynomial time; the witness itself can be arbitrarily complicated to build. It's clear that PCP(0, 0), the set of languages that can be checked probabilistically with 0 bits of randomness and 0 bits of certificate, is equal to P: the verifier has no additional tools. PCP(O(log(n)), 0) is also equal to P: a deterministic verifier could just enumerate all sequences of log(n) bits. The same is true if the verifier has access to log(n) bits of the witness, but no randomness: the verifier can enumerate all witnesses of log(n) bits. The magic of the PCP theorem is that PCP(O(log(n)), O(1)) = NP! That is, if I have access to log(n) random bits and a suitable proof that a given instance is in a language like SAT (or any other language in NP), I can verify that proof in polynomial time, by looking at a constant number of bits of that proof. The key is that we have enough bits of randomness to choose randomly from all the bits in the witness. Intuitively, I still have a hard time believing the PCP construction works. However, it does hint at how randomness can give us more leverage. That said, I definitely agree that most uses of randomness seem unwarranted in practice, especially if we understand the problem domain very well. But then again, what if we don't? I would often rather have a consistently robust but suboptimal solution than one that is optimal in a small range of parameters but fails hard outside of the expected input.