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