A generic time hierarchy for semantic models with one bit of advice

Abstract. We show that for any reasonable semantic model of compu-tation and for any positive integer a and rationals 1 ≤ c < d, there exists a language computable in time nd with a bits of advice but not in time nc 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 ef-ficient universal machine that can be complemented within the model in exponential time and if it is efficiently closed under deterministic trans-ducers. Our result implies the first such hierarchy theorem for randomized ma-chines 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 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 com-putable in polynomial time with one bit of advice but not in time nc with a log n bits of advice. In particular, we obtain such separation for randomized and quantum machines with two-sided error. For random-ized 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 nc with a(logn)1/c bits of advice.