A Probabilistic-Time Hierarchy Theorem
for "Slightly Non-Uniform" Algorithms
Boaz Barak
Abstract
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 BPP is contained in
the class BPtime(n). In fact, it may even be that the class
BPtime(n^{log n}) is contained in the class 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:N-->N where log log n <
a(n) < log n, and for every constant d >= 1,
BPtime(n^d)_{/a(n)} is properly contained in 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_{/log log n} is
not contained in the class BPtime(n^d)_{/log n} for
every constant d.
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.
Versions
-
To appear in RANDOM 2002
- Full version
[postscript]
home | research | links | cv | pictures
|