TR14-171 Authors: Lance Fortnow, Rahul Santhanam

Publication: 11th December 2014 15:18

Downloads: 998

Keywords:

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