<p><em>Disclaimer:</em> 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 <span class="math-container">$\mathsf{NC}$</span> hierarchy is non-negligible. If you observe that it is the case, please tell me and I'll update my answer.</p>

<ul>
<li><p>The report <a href="https://repository.upenn.edu/cgi/viewcontent.cgi?referer=https://www.google.fr/&amp;httpsredir=1&amp;article=1444&amp;context=cis_reports" rel="noreferrer">Parallel Algorithms for Depth-First Search</a> discusses known parallel algorithms for DFS on various types of graphs. The list given on pages 9-10 indicates several algorithms in <span class="math-container">$\mathsf{NC} \setminus \mathsf{NC}_2$</span>, such as DFS for planar undirected graphs, or in <span class="math-container">$\mathsf{RNC} \setminus \mathsf{RNC}_2$</span>, such as DFS for general undirected graphs.</p></li>
<li><p>With a quick search, I could not find papers improving over the parallel algorithms for sparse multivariate polynomial interpolation over finite fields of <a href="https://www.researchgate.net/profile/Dima_Grigoriev/publication/220617525_Fast_Parallel_Algorithms_for_Sparse_Multivariate_Polynomial_Interpolation_over_Finite_Fields/links/0c960521384c54bb6f000000.pdf" rel="noreferrer">this paper</a>, which is in <span class="math-container">$\mathsf{NC}_3$</span>. However, several papers that could possibly have been relevant were behind a paywall.</p></li>
<li><p>Computing all maximal cliques in a graph is in <span class="math-container">$\mathsf{NC} \setminus \mathsf{NC}_2$</span> when the number of maximal clique is polynomially bounded, according to <a href="https://link.springer.com/chapter/10.1007%2F3-540-19487-8_16?LI=true" rel="noreferrer">this paper</a>.</p></li>
<li><p>The maximal path problem seems to be <a href="https://link.springer.com/article/10.1007/BF02579320" rel="noreferrer">in <span class="math-container">$\mathsf{NC}_5$</span></a> for general (undirected) graphs, I've not found a faster parallel algorithms without restrictions on the underlying graph.</p></li>
</ul>

<p>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. <a href="https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/82762/1/0796-05.pdf" rel="noreferrer">this paper</a> mentions a randomized polytime algorithms in parallel time <span class="math-container">$O(\log^6n)$</span>). <a href="https://pdfs.semanticscholar.org/06da/e10dc61bdf1e32480ddb0cbe680d94f640f9.pdf" rel="noreferrer">This paper</a> also mention solving classes of CSPs problems that arise in computer vision application, in parallel time <span class="math-container">$O(\log^3n)$</span>.</p>

CC BY-SA 4.0
2018-09-18T17:25:11.770Z
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.
Joshua Grochow
CC BY-SA 4.0
2018-09-18T17:46:18.910Z
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.
Geoffroy Couteau
CC BY-SA 4.0
2017-12-22T12:58:14.147Z
2018-10-20T01:50:47.293Z
2018-10-20T01:50:47.293Z
Geoffroy Couteau
<p>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. </p>

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

CC BY-SA 3.0
2016-07-21T20:30:04.480Z
See [this question](http://cstheory.stackexchange.com/q/11227/) and Josh's answer to it.
Kaveh
CC BY-SA 3.0
2016-07-21T21:25:19.187Z
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}$.
xal
CC BY-SA 3.0
2017-12-20T19:32:30.913Z
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?
Joshua Grochow
CC BY-SA 3.0
2017-12-21T00:29:42.863Z
@Josh, I don't see any problem with doing so. We have asked authors to split the questions into separate posts before.
Kaveh
CC BY-SA 3.0
2017-12-22T05:30:57.800Z
Thanks for asking Josh, I split the question here: https://cstheory.stackexchange.com/q/39831/40340
xal
<complexity-classes><dc.parallel-comp>
Problems in NC not known to lie in NC2
xal
# Problems in NC not known to lie in NC2

(Asked by: username_0 on 2016-07-21)

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

**Tags:** complexity-classes, dc.parallel-comp
> **Comments:**
> **username_1**: See [this question](http://cstheory.stackexchange.com/q/11227/) and Josh's answer to it.  
> **username_0**: 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}$.  
> **username_2**: 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?  
> **username_1**: @Josh, I don't see any problem with doing so. We have asked authors to split the questions into separate posts before.  
> **username_0**: Thanks for asking Josh, I split the question here: https://cstheory.stackexchange.com/q/39831/40340  

---

## 1 answers

### Answer by username_3 on 2017-12-22. Score: 14

*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](https://repository.upenn.edu/cgi/viewcontent.cgi?referer=https://www.google.fr/&httpsredir=1&article=1444&context=cis_reports) 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](https://www.researchgate.net/profile/Dima_Grigoriev/publication/220617525_Fast_Parallel_Algorithms_for_Sparse_Multivariate_Polynomial_Interpolation_over_Finite_Fields/links/0c960521384c54bb6f000000.pdf), 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](https://link.springer.com/chapter/10.1007%2F3-540-19487-8_16?LI=true).
* The maximal path problem seems to be [in $\mathsf{NC}\_5$](https://link.springer.com/article/10.1007/BF02579320) 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](https://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/82762/1/0796-05.pdf) mentions a randomized polytime algorithms in parallel time $O(\log^6n)$). [This paper](https://pdfs.semanticscholar.org/06da/e10dc61bdf1e32480ddb0cbe680d94f640f9.pdf) also mention solving classes of CSPs problems that arise in computer vision application, in parallel time $O(\log^3n)$.

> **Comments:**
> **username_2**: 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.  
> **username_3**: 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.  

---

