tablishing time hierarchies for non-syntactic models with
small advice.
In this talk we survey these results and present a generic theorem that c

aptures and strengthens all of them. We show that for virtually any semanti

c model of computation and for any rationals 1 <= c < d there exists a lan

guage computable in time n%5Ed with one bit of advice but not in time n%5Ec
with one bit of advice where we call a model semantic if there exists a c

omputable enumeration that contains all machines in the model but may also

contain others.

Our result implies the first such hierarchy theorem

for
randomized machines with zero-sided error quantum machines with on

e-
or zero-sided error unambiguous machines symmetric alternation Ar

thur-Merlin games of any signature etc. Our argument also yields considera

bly simpler proofs of earlier hierarchy theorems with one bit of advice for
randomized or quantum machines with two-sided error.

This is joint