 Probabilistic and deterministic Turing machines (DTMs) have different success criteria. A successful deterministic algorithm for a given problem is guaranteed to yield the correct answer given its input. Of a successful probabilistic algorithm, on the other hand, we only demand that it yield a correct answer with “high” probability (minimally, we demand that it be strictly greater than 1/2). It was believed, until relatively recently, that for some problems (see, e.g. Rabin 1976) probabilistic algorithms are dramatically more efficient than any deterministic alternatives; in other words that the set or “class” of problems efficiently solvable by PTM is larger than the class of problems efficiently solvable by DTM. Fascinatingly, evidence has been mounting in recent years (e.g. Agrawal, Kayal, and Saxena 2004) that this is not the case, and it is now believed that the PTM model in fact does not offer a computational advantage in this sense over the DTM model (Arora and Barak 2009 Ch. 20). Probabilistic (Turing) computation is nevertheless interesting to consider, because abstractly a quantum computer is just a variation on the PTM which does appear to offer computational advantages over deterministic computation, although as already mentioned this conjecture still awaits a proof. See Hagar (2007) and Cuffaro (2018b) for divergent opinions over what this purported quantum computational advantage tells us about the theory of computational complexity as a whole.