W artykule „A Compendium of Problems Complete for P” autorstwa Greenlawa, Hoovera i Ruzzo (PS) (PDF) znajduje się lista problemów w P, które nie są znane w NC i nie są znane jako P-complete . (Ta lista obejmuje wszystkie otwarte problemy w doskonałej ankiecie przeprowadzonej przez Karpa i Ramachandrana .) Lista otwartych problemów zaczyna się na stronie 89.
Ile problemów z tej listy zostało rozwiązanych (tzn. Wykazano, że są P-kompletne lub w NC)? Zgaduję, że nie zostało zbyt wiele rozwiązanych w ciągu ostatnich 19 lat, więc (mam nadzieję) nie powinno to zmienić się w dużą listę.
To najnowsza lista, jaką udało mi się znaleźć. Docenione zostaną również wskaźniki do bardziej aktualnej listy!
EDYCJA: András Salamon wskazuje, że istnieje podręcznik tych samych autorów, który ma nieco dłuższą listę. To jest plik PDF książki. Otwarte problemy zaczynają się na stronie 237.