Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR14-171 | 11th December 2014 13:23

Hierarchies Against Sublinear Advice


Authors: Lance Fortnow, Rahul Santhanam
Publication: 11th December 2014 15:18
Downloads: 1436


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

ISSN 1433-8092 | Imprint