# Problems between NC and P: How many have been resolved from this list?

In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo (PS) (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.) 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. The open problems start on page 237.

• @Robin, Please CW. – Mohammad Al-Turkistany Sep 15 '10 at 2:48
• @turkistany: Since this very similar question (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 Sep 15 '10 at 3:58
• @András: Thanks. I'll add it to my post. It looks like a slightly longer list by the same authors. – Robin Kothari Sep 15 '10 at 19:43

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.