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?


1 Answer 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.