P-RAM vs. RP-RAM

In this paper, we close Simon's open problem by fully characterising the class of languages recognisable in polynomial time by each of the RAMs regarding which the question was posed. We show that for some of these stochasticity does not entail any advantage, but, more interestingly, we show that for others it does. These results carry over also to BPP-like and coRP-like acceptance criteria.