Threshold machines are Turing machines whose acceptance is determined by what portion of the machine's computation paths are accepting paths. Probabilistic machines are Turing machines whose acceptance is determined by the probability weight of the machine's accepting computation paths. Simon proved that for unbounded-error polynomial-time machines these two notions yield the same class, PP. Perhaps because Simon's result seemed to collapse the threshold and probabilistic modes of computation, the relationship between threshold and probabilistic computing for the case of bounded error has remained unexplored.

In this paper, we compare the bounded-error probabilistic class BPP with the analogous threshold class, BPP_path, and, more generally, we study the structural properties of BPP_path. We prove that BPP_path contains both NP^BPP and P^NP[log], and that BPP_path is contained in P^{Sigma_2[log]}, BPP^NP, and PP. We conclude that, unless the polynomial hierarchy collapses, bounded-error threshold computation is strictly more powerful than bounded-error probabilistic computation.

We also consider the natural notion of secure
access to a database: an adversary who watches the queries should
gain no information about the input other than perhaps its
length.
We show, for both BPP and BPP_path, that if there
is any database for which this formalization
of security differs from the security given by
oblivious database access, then P is different from PSPACE.
It follows that if any set lacking small circuits
can be securely accepted, then
P is different from PSPACE.