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].

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].