# How big is NSC^k?

It is well known that $\mathsf{NL} \subseteq \mathsf{NC} \subseteq \mathsf{P}$, both inclusions conjectured to be proper. On the other hand $\mathsf{NP} \supseteq \mathsf{P}$, also probably a proper inclusion. There are classes naturally interpolating between $\mathsf{NL}$ and $\mathsf{NP}$, namely $\mathsf{NSC}^k$, languages decidable by non-deterministic Turing machines in simultaneous polynomial time complexity and $O(\log^k n)$ space complexity. How big are these classes? We have $\mathsf{NSC}^k \subseteq \mathsf{polyL}$ since $NSPACE(O(\log^k n)) \subseteq DSPACE(O(\log^{2k} n))$

Do we have $\mathsf{NSC}^k \subseteq \mathsf{NC}$? $\mathsf{NSC}^k \subseteq \mathsf{P}$? $\mathsf{NSC}^k = \mathsf{NP}$? What is is known about these questions for different values of $k$ > 1?

-

This is not an answer to your exact question, but perhaps you may find this helpful.

You might have a slightly easier time finding results for the class of languages decided by nondeterministic $\mathsf{NC}$ circuit families augmented with a polylogarithmic number of nondeterministic bits, called $\mathsf{NNC}(\mathrm{polylog})$ by Wolf or $\mathsf{GC}(\mathrm{polylog}, \mathsf{NC})$ by Cai and Chen (there are many other names). These complexity classes live between $\mathsf{NC}$ and $\mathsf{NP}$ and are also contained in $\mathsf{polyL}$.

Wolf showed that $\mathsf{NP} = \mathsf{NNC}(\mathrm{poly})$ (that is, $\mathsf{NC}$ circuits with a polynomial amount of nondeterminism) and $\mathsf{NC} = \mathsf{NNC}(\log)$ (that is, $\mathsf{NC}$ circuits with a logarithmic amount of nondeterminism).

Again, your question is about a family of complexity classes allowing polylogarithmic time and my answer is about a family of complexity classes allowing polylogarithmic nondeterminism, but it may be a start.

-