Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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