15
$\begingroup$

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}$?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ See this question and Josh's answer to it. $\endgroup$
    – Kaveh
    Commented Jul 21, 2016 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
    Commented Jul 21, 2016 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$
    – Joshua Grochow
    Commented Dec 20, 2017 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
    Commented Dec 21, 2017 at 0:29
  • 1
    $\begingroup$ Thanks for asking Josh, I split the question here: cstheory.stackexchange.com/q/39831/40340 $\endgroup$
    – xal
    Commented Dec 22, 2017 at 5:30

1 Answer 1

Reset to default
14
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 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$
    – Joshua Grochow
    Commented Sep 18, 2018 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$
    – Geoffroy Couteau
    Commented Sep 18, 2018 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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