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}$. The best known earlier separation
\cite{Fortnow-Santhanam-Trevisan04} could only handle $o(\log(n))$ bits of
advice in the lower bound.

We generalize our hierarchy theorem to work for other syntactic
complexity
measures between polynomial time and polynomial space, including alternating
polynomial time with any fixed number of alternations. We also use our technique to derive an {\it almost-everywhere} hierarchy theorem for non-deterministic classes which use a sublinear
amount of non-determinism, i.e., the lower bound holds on all but finitely
many input lengths rather than just on infinitely many.

As an application of our main result, we derive a new lower bound for $\NP$
against $\NP$-uniform non-deterministic circuits of size $O(n^k)$ for any fixed $k$. This
result is a significant strengthening of a result of Kannan
\cite{Kannan82}, which states that not all of $\NP$ can be solved with
$\P$-uniform circuits of size $O(n^k)$ for any fixed $k$.