<p>BTW: The list of known CC-complete problems has grown since both versions of the book.   See <a href="http://onlinelibrary.wiley.com/doi/10.1002/cplx.20238/abstract">this paper</a> by Greenlaw and Kanlabutra.</p>

CC BY-SA 2.5
2010-09-18T04:11:14.000Z
2010-09-18T04:11:14.000Z
Paul Beame
<p>The parallel complexity of the graph closure problem (problem $B.1.4$, posed by Khuller) was resolved By Angelo Monti. He showed that the graph closure problem is P-complete.</p>

<p><a href="http://dx.doi.org/10.1016/0020-0190(96)00027-0" rel="nofollow">Angelo Monti, On the computational complexity of graph closures </a>
Information Processing Letters, Volume 57, Issue 6, 25 March 1996, Pages 291–295.</p>

CC BY-SA 3.0
2010-09-16T18:22:02.510Z
2015-12-24T17:49:57.807Z
2015-12-24T17:49:57.807Z
Mohammad Al-Turkistany
<p>In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo <a href="ftp://ftp.cs.washington.edu/tr/1991/05/UW-CSE-91-05-01.PS.Z">(PS)</a> <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9269&amp;rep=rep1&amp;type=pdf">(PDF)</a>, there is a list of problems in P that are not known to be in NC and not known to be P-complete either. (This list subsumes all the open problems in <a href="http://www2.cs.pitt.edu/~kirk/cs1510/ParallelAlgorithmsSurvey.pdf">the excellent survey by Karp and Ramachandran</a>.) The open problems list starts on page 89. </p>

<p>How many problems from this list have been resolved (i.e., shown to be P-complete or in NC)? I'm guessing not too many have been solved in the last 19 years, so this (hopefully) shouldn't turn into a big-list.</p>

<p>That's the most recent list I could find. Pointers to a more up-to-date list would also be appreciated!</p>

<p>EDIT: András Salamon points out that there is a textbook by the same authors which has a slightly longer list. <a href="http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/limits.pdf">This is a PDF of the book.</a> The open problems start on page 237.</p>

CC BY-SA 2.5
2010-09-15T02:48:43.793Z
@Robin, Please CW.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-15T03:58:36.210Z
@turkistany: Since this very similar question (http://cstheory.stackexchange.com/q/1265/206) was deemed not necessarily CW, I'm not sure if this should be CWed. I'm going to follow the FAQ's "When in doubt, do not mark a question CW" policy and wait for more opinions.
Robin Kothari
CC BY-SA 2.5
2010-09-15T19:43:28.533Z
@András: Thanks. I'll add it to my post. It looks like a slightly longer list by the same authors.
Robin Kothari
<cc.complexity-theory><open-problem><circuit-complexity>
Problems between NC and P: How many have been resolved from this list?
Robin Kothari
# Problems between NC and P: How many have been resolved from this list?

(Asked by: username_0 on 2010-09-15)

In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo [(PS)](ftp://ftp.cs.washington.edu/tr/1991/05/UW-CSE-91-05-01.PS.Z) [(PDF)](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.9269&rep=rep1&type=pdf), there is a list of problems in P that are not known to be in NC and not known to be P-complete either. (This list subsumes all the open problems in [the excellent survey by Karp and Ramachandran](http://www2.cs.pitt.edu/~kirk/cs1510/ParallelAlgorithmsSurvey.pdf).) The open problems list starts on page 89.

How many problems from this list have been resolved (i.e., shown to be P-complete or in NC)? I'm guessing not too many have been solved in the last 19 years, so this (hopefully) shouldn't turn into a big-list.

That's the most recent list I could find. Pointers to a more up-to-date list would also be appreciated!

EDIT: András Salamon points out that there is a textbook by the same authors which has a slightly longer list. [This is a PDF of the book.](http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/limits.pdf) The open problems start on page 237.

**Tags:** cc.complexity-theory, open-problem, circuit-complexity
> **Comments:**
> **username_1**: @Robin, Please CW.  
> **username_0**: @turkistany: Since this very similar question (http://cstheory.stackexchange.com/q/1265/206) was deemed not necessarily CW, I'm not sure if this should be CWed. I'm going to follow the FAQ's "When in doubt, do not mark a question CW" policy and wait for more opinions.  
> **username_0**: @András: Thanks. I'll add it to my post. It looks like a slightly longer list by the same authors.  

---

## 2 answers

### Answer by username_2 on 2010-09-18. Score: 13

BTW: The list of known CC-complete problems has grown since both versions of the book. See [this paper](http://onlinelibrary.wiley.com/doi/10.1002/cplx.20238/abstract) by Greenlaw and Kanlabutra.


---

### Answer by username_1 on 2010-09-16. Score: 11

The parallel complexity of the graph closure problem (problem $B.1.4$, posed by Khuller) was resolved By Angelo Monti. He showed that the graph closure problem is P-complete.

[Angelo Monti, On the computational complexity of graph closures](http://dx.doi.org/10.1016/0020-0190(96)00027-0) 
Information Processing Letters, Volume 57, Issue 6, 25 March 1996, Pages 291–295.


---

