I know these relations : \\begin{gather} \\mathrm{NC}^1 \\subseteq \\mathrm{NC}^
ID: 653010 • Letter: I
Question
I know these relations :
egin{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|)$
Explanation / Answer
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 eq 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$.