3 ms·
> If you want to use a different computation model, you have to explicitly define it. Probabilistic Turing machine are sufficiently standard and well known. T
by eru 6y ago
> If you want to use a different computation model, you have to explicitly define it.
Probabilistic Turing machine are sufficiently standard and well known. They (or the random-access machine equivalent) are basically the implied context whenever you talk about randomized algorithm.
See https://en.wikipedia.org/wiki/Probabilistic_Turing_machine https://en.wikipedia.org/wiki/Probabilistic_Turing_machine and https://en.wikipedia.org/wiki/Randomized_algorithm#Computational_complexity https://en.wikipedia.org/wiki/Randomized_algorithm#Computati...