Problemy między NC i P: Ile zostało rozwiązanych z tej listy?

20

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.

Robin Kothari
źródło
@ Robin, proszę CW.
Mohammad Al-Turkistany
5
@turkistany: Ponieważ to bardzo podobne pytanie ( cstheory.stackexchange.com/q/1265/206 ) zostało uznane za niekoniecznie CW, nie jestem pewien, czy to powinno być CWed. Będę postępować zgodnie z polityką FAQ „W razie wątpliwości nie zaznaczaj pytania CW” i czekam na więcej opinii.
Robin Kothari,
@ András: Dzięki. Dodam to do mojego postu. Wygląda na nieco dłuższą listę tych samych autorów.
Robin Kothari,

Odpowiedzi:

12

BTW: Lista znanych problemów z kompletnym CC wzrosła od czasu obu wersji książki. Zobacz ten artykuł autorstwa Greenlaw i Kanlabutra.

Paul Beame
źródło