HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to compare algorithms in class NC time complexity with other classes?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
withothertimealgorithmsclasseshowcompareclasscomplexity

Problem

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|)$

Solution

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$.

Context

StackExchange Computer Science Q#22709, answer score: 5

Revisions (0)

No revisions yet.