4 ms·
My point that probably P=RP=BPP is that randomness probably doesn't give you any computational power, but not for the reason Eliezer gives (that we can come up
by alexbecker 12y ago
My point that probably P=RP=BPP is that randomness probably doesn't give you any computational power, but not for the reason Eliezer gives (that we can come up with an equally good structured way to do things), but rather because we can make deterministic algorithms which look sufficiently like they're using randomness.
I don't think your analogy really holds up--monads are just an abstraction implemented on a turing machine, they can't possibly give you anything a turing machine can't, since you are actually using a turing machine. With randomness you are in principal actually extending a turing machine, although it's an open question whether or not this actually gains you anything.