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.