I know these relations :

\begin{gather} \mathrm{NC}^1 \subseteq \mathrm{NC}^2 \subseteq \dots \subseteq \mathrm{NC}^i \subseteq \dots \subseteq \mathrm{NC} \\ \mathrm{NC}^i \subseteq \mathrm{AC}^i \subseteq \mathrm{NC}^{i+1} \\ \mathrm{NC}^1 \subseteq \mathrm{L} \subseteq \mathrm{NL} \subseteq \mathrm{AC}^1 \subseteq \mathrm{NC}^2 \subseteq \mathrm{P} \end{gather}

But I don't know how to compare an algorithm with time complexity of $\mathrm{NC}^i$ to an algorithm with Polynomial complexity?

For example, Topological sort $\mathrm{NC}^2$ with BFS $\mathcal{O}(|V| + |E|)$


The class NC is by definition a subset of P, since it consists of uniform polynomial size circuits with some restrictions (namely, polylogarithmic depth). It is unknown whether $NC \neq P$, but this is strongly suspected.

Let me comment that $O(NC^2)$ is a syntax mismatch since $NC^2$ is a complexity class rather than a function. We simply say that topological sort is in $NC^2$.

  • 3
    $\begingroup$ That's not a mechanical process, since by putting something in the NC hierarchy you're trying to optimize circuit depth, while in algorithms we often try to optimize running time. $\endgroup$ – Yuval Filmus Mar 17 '14 at 14:23
  • $\begingroup$ You might add how depth of a circuit and exponent of a polynomial time algorithm are related. $\endgroup$ – frafl Apr 2 '14 at 13:46
  • $\begingroup$ If the circuit is uniform then the size of the circuit (corresponding to time) is exponential in its depth, so only uniform NC$^1$ is in P due to the depth. Fortunately, circuits in NC also have to be polynomial size. So you cannot generally tell from the depth anything about the running time. $\endgroup$ – Yuval Filmus Apr 2 '14 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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