20

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 Kothari
  • 13,617
  • 2
  • 60
  • 116

2 Answers2

12

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

Paul Beame
  • 641
  • 4
  • 5
10

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.

András Salamon
  • 19,000
  • 3
  • 64
  • 150
Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149