20
$\begingroup$

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.

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

BTW: The list of known CC-complete problems has grown since both versions of the book. See this paper by Greenlaw and Kanlabutra.

Improve this answer
$\endgroup$
0
10
$\begingroup$

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 Information Processing Letters, Volume 57, Issue 6, 25 March 1996, Pages 291–295.

Improve this answer
$\endgroup$

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.