Hierarchies against Sublinear Advice
We strengthen the non-deterministic time hierarchy theorem to show that the lower bound holds against sublinear advice. More formally, we show that for any constants c and d such that 0 < 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 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 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 in finitely 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, which states that not all of NP can be solved with P-uniform circuits of size O(n^k) for any fixed k.