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 ... more >>>

We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following. Let s(n) ... more >>>