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. In 1975, 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, $\bpppath$, and, more generally, we study the structural properties of $\bpppath$. We prove that $\rm BPP_{path}$ contains both $\np^{\bpp}$ and $\p^{\rm NP[\log]}$ and that $\rm BPP_{path}$ is contained in $\p^{{\rm \Sigma}_2^p[\log]}$, $\rm 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 $\bpppath$ that if there is any database for which this formalization of security differs from the security given by oblivious database access, then $\p\neq \pspace$\@. It follows that if any set lacking small circuits can be securely accepted, then $\p\neq\pspace$.

We investigate classes of sets that can be decided by bounded truth-table reductions to an NP set in which evaluators donothave full access to the answers to the queries but get only restricted information such as the number of queries that are in the oracle set or even just this number modulom, for somem⩾2. We also investigate the case in which evaluators are nondeterministic. We show that when we vary the information that the evaluators get, this can change the resulting power of the evaluators. We locate all these classes within levels of the Boolean hierarchy which allows us to compare the complexity of such classes.