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

<p>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 <a href="http://dx.doi.org/10.1016/0304-3975%2892%2900014-I" rel="nofollow">Wolf</a> or $\mathsf{GC}(\mathrm{polylog}, \mathsf{NC})$ by <a href="http://dx.doi.org/10.1137/S0097539793258295" rel="nofollow">Cai and Chen</a> (there are many other names). These complexity classes live between $\mathsf{NC}$ and $\mathsf{NP}$ and are also contained in $\mathsf{polyL}$.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2013-01-30T00:14:07.630Z
2013-01-30T00:14:07.630Z
argentpepper
<p>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))$</p>

<blockquote>
  <p>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?</p>
</blockquote>

<cc.complexity-theory><space-bounded><nondeterminism>
How big is NSC^k?
Vanessa
# How big is NSC^k?

(Asked by: username_0 on 2012-12-29)

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?

**Tags:** cc.complexity-theory, space-bounded, nondeterminism

---

## 1 answers

### Answer by username_1 on 2013-01-30. Score: 2

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](http://dx.doi.org/10.1016/0304-3975%2892%2900014-I) or $\mathsf{GC}(\mathrm{polylog}, \mathsf{NC})$ by [Cai and Chen](http://dx.doi.org/10.1137/S0097539793258295) (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.


---

