- Authors: D. van Melkebeek and K. Pervyshev.
- Reference:
Computational Complexity, 16: 139-179, 2007.
Special issue for selected papers from the
21st IEEE Conference on Computational Complexity.
- Earlier version:
Abstract
We show that for any reasonable semantic model of computation and for
any positive integer a and rationals 1 ≤ c < d,
there exists a language
computable in time nd with one bit of advice
but not in
time nc with a bits of advice.
Our result implies the first such hierarchy theorem for randomized
machines with zero-sided error, quantum machines with one- or zero-sided
error, unambiguous machines, symmetric alternation,
Arthur-Merlin games of any signature, etc.
Our argument yields considerably simpler proofs of known hierarchy
theorems with one bit of advice for randomized and quantum machines with
two-sided error.
Our paradigm also allows us to derive stronger separation results
in which the machine with the smaller running time can receive more
advice than the one with the larger running time. We present a unified
way to derive such results for randomized and quantum machines with
two-sided error and for randomized machines with one-sided error.
