| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4952002 | Theoretical Computer Science | 2017 | 13 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Michael Brand,