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.
źródło
Odpowiedzi:
BTW: Lista znanych problemów z kompletnym CC wzrosła od czasu obu wersji książki. Zobacz ten artykuł autorstwa Greenlaw i Kanlabutra.
źródło
Angelo Monti, O złożoności obliczeniowej zamknięć grafów Information Processing Letters, tom 57, wydanie 6, 25 marca 1996, strony 291–295.
źródło