In this work we prove that a hierarchy theorem does hold for “slightly non-uniform” probabilistic machines. Namely, we prove that for every function a:ℕ→ℕ where log log n ≤ a(n) ≤ logn, and for every constant d≥ 1,

$ BPtime(n^d )_{/a(n)} \mathop \subset \limits_ \ne BPP_{/a(n)} $ BPtime(n^d )_{/a(n)} \mathop \subset \limits_ \ne BPP_{/a(n)}

here BPtime(t(n))/a(n) is defined to be the class of languages that are accepted by probabilistic Turing machines of running time t(n) and description size a(n). We actually obtain the stronger result that the class BPP/loglogn is not contained in the class BPtime(n ^d)/logn for every constant d ≥ 1.

We also discuss conditions under which a hierarchy theorem can be proven for fully uniform Turing machines. In particular we observe that such a theorem does hold if BPP has a complete problem.