We strengthen the non-deterministic time hierarchy theorem of
\cite{Cook72, Seiferas-Fischer-Meyer78, Zak83} to show that the lower bound
holds against sublinear advice. More formally, we show that for any constants
$c$ and $d$ such that $1 \leq c < d$, there is a language in $\NTIME(n^d)$
which is not in $\NTIME(n^c)/n^{1/d}$. ... more >>>