# zbMATH — the first resource for mathematics

A probabilistic-time hierarchy theorem for “slightly non-uniform” algorithms. (English) Zbl 1028.68058
Rolim, José D. P. (ed.) et al., Randomization and approximation techniques in computer science. 6th international workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2483, 194-208 (2002).
Summary: Unlike other complexity measures such as deterministic and nondeterministic time and space, and non-uniform size, it is not known whether probabilistic time has a strict hierarchy. For example, as far as we know it may be that $$\mathbf {BPP}$$ is contained in the class $$\mathbf {BPtime}(n)$$. In fact, it may even be that the class $$\mathbf {BPtime}(n^{\log n})$$ is contained in the class $$\mathbf {BPtime}(n)$$.
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:\mathbb {N}\rightarrow \mathbb {N}$$ where $$\log\log n \leq a(n) \leq \log n$$, and for every constant $$d \geq 1$$, $$\mathbf {BPtime}(n^d)_{/a(n)} \subsetneqq \mathbf {BPP}_{/a(n)}$$ here $$\mathbf {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 $$\mathbf {BPP}_{/\log\log n}$$ is not contained in the class $$\mathbf {BPtime}(n^d)_{/\log n}$$ for every constant $$d \geq 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 $$\mathbf {BPP}$$ has a complete problem.
For the entire collection see [Zbl 1001.00041].

##### MSC:
 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
Full Text: