TR05-111 Authors: Dieter van Melkebeek, Konstantin Pervyshev

Publication: 8th October 2005 19:21

Downloads: 2030

Keywords:

We show that for any reasonable semantic model of computation and for

any positive integer $a$ and rationals $1 \leq c < d$, there exists a language

computable in time $n^d$ with $a$ bits of advice but not in time $n^c$

with $a$ bits of advice. A semantic model is one for which there exists a

computable enumeration that contains all machines in the model but may

also contain others. We call such a model reasonable if it has an

efficient universal machine that can be complemented within the model

in exponential time and if it is efficiently closed under deterministic

transducers.

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,

interactive proof protocols with one or multiple provers, etc. Our

argument yields considerably simpler proofs of known hierarchy

theorems with one bit of advice for randomized or quantum machines with

two-sided error and randomized machines with one-sided error.

Our paradigm also allows us to derive stronger separation results in a

unified way. For models that have an efficient universal machine that can be

simulated deterministically in exponential time and that are efficiently

closed under randomized reductions with two-sided error, we establish the

following: For any constants $a$ and $c$, there exists a language computable

in polynomial time with one bit of advice but not in time $n^c$ with

$a \log n$ bits of advice.

In particular, we obtain such separation for randomized and quantum

machines with two-sided error.

For randomized machines with one-sided error, we get that for any

constants $a$ and $c$ there exists a language computable in polynomial

time with one bit of advice but not in time $n^c$ with $a (\log n)^{1/c}$

bits of advice.