Are there interesting problems that are in $\mathsf{NC}$ but not known to be in $\mathsf{NC^{2}}$? In the paper 'A Taxonomy of Problems With Fast Parallel Algorithms', Cook mentions that MIS was known to only be in $\mathsf{NC^{5}}$ but this has since been brought down to $\mathsf{NC^{2}}$. I am wondering if there are any other problems with polylog-depth parallel algorithms where we seem to be stuck on improving the depth.

To narrow down even further, are there any problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$?

  • 1
    $\begingroup$ See this question and Josh's answer to it. $\endgroup$
    – Kaveh
    Jul 21 '16 at 20:30
  • $\begingroup$ I missed that completely Kaveh---thanks! The answer's last paragraph on $\mathsf{NL}=\mathsf{coNL}$ and the corresponding hierarchy collapse gives useful intuition for the state of $\mathsf{NC}$. $\endgroup$
    – xal
    Jul 21 '16 at 21:25
  • $\begingroup$ I actually was just wondering about your final question; I think it would be worth posting as a separate question (since it is technically a different question, and independent from the question in your title). xal, would you be open to posting the question of problems in $\mathsf{NC}^2$ not known to be in $(\mathsf{AC}^1 \cup \mathsf{DET})$ as a separate question? And @Kaveh, what do you think about doing so from a procedural perspective? $\endgroup$ Dec 20 '17 at 19:32
  • $\begingroup$ @Josh, I don't see any problem with doing so. We have asked authors to split the questions into separate posts before. $\endgroup$
    – Kaveh
    Dec 21 '17 at 0:29
  • 1
    $\begingroup$ Thanks for asking Josh, I split the question here: cstheory.stackexchange.com/q/39831/40340 $\endgroup$
    – xal
    Dec 22 '17 at 5:30

Disclaimer: I'm not an expert in fast parallel algorithms, hence the probability that I missed more recent results that put the problems I mention in lower levels of the $\mathsf{NC}$ hierarchy is non-negligible. If you observe that it is the case, please tell me and I'll update my answer.

  • The report Parallel Algorithms for Depth-First Search discusses known parallel algorithms for DFS on various types of graphs. The list given on pages 9-10 indicates several algorithms in $\mathsf{NC} \setminus \mathsf{NC}_2$, such as DFS for planar undirected graphs, or in $\mathsf{RNC} \setminus \mathsf{RNC}_2$, such as DFS for general undirected graphs.

  • With a quick search, I could not find papers improving over the parallel algorithms for sparse multivariate polynomial interpolation over finite fields of this paper, which is in $\mathsf{NC}_3$. However, several papers that could possibly have been relevant were behind a paywall.

  • Computing all maximal cliques in a graph is in $\mathsf{NC} \setminus \mathsf{NC}_2$ when the number of maximal clique is polynomially bounded, according to this paper.

  • The maximal path problem seems to be in $\mathsf{NC}_5$ for general (undirected) graphs, I've not found a faster parallel algorithms without restrictions on the underlying graph.

Other potential candidates might include algorithms for finding perfect matchings in specific types of graphs, or algorithms for finding a maximal tree cover in arbitrary graphs (e.g. this paper mentions a randomized polytime algorithms in parallel time $O(\log^6n)$). This paper also mention solving classes of CSPs problems that arise in computer vision application, in parallel time $O(\log^3n)$.

  • 1
    $\begingroup$ Interesting! Do you know if any of these are complete (or conjectured to be complete) for these higher levels of the NC hierarchy? It'd be nice to have such natural examples on hand. $\endgroup$ Sep 18 '18 at 17:25
  • $\begingroup$ Unfortunately I have no idea about that, the papers I list above do not mention anything of the kind (as far as I can see). All of this is very far from my area of expertise; I just did a literature search to answer OP's question since I found it very interesting, but my limited knowledge does not give me any clear intuition about the hardness of these problems. $\endgroup$ Sep 18 '18 at 17:46

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.