Probleme zwischen NC und P: Wie viele wurden aus dieser Liste gelöst?

20

In der Arbeit "Ein Kompendium von Problemen, die für P vollständig sind" von Greenlaw, Hoover und Ruzzo (PS) (PDF) gibt es eine Liste von Problemen in P, von denen nicht bekannt ist, dass sie in NC vorliegen, und von denen auch nicht bekannt ist, dass sie P-vollständig sind . (Diese Liste fasst alle offenen Probleme in der hervorragenden Umfrage von Karp und Ramachandran zusammen .) Die Liste der offenen Probleme beginnt auf Seite 89.

Wie viele Probleme aus dieser Liste wurden behoben (dh als P-vollständig oder in NC angezeigt)? Ich vermute nicht, dass in den letzten 19 Jahren zu viele Probleme gelöst wurden, daher sollte dies (hoffentlich) nicht zu einer großen Liste werden.

Das ist die neueste Liste, die ich finden konnte. Hinweise auf eine aktuellere Liste wären auch willkommen!

EDIT: András Salamon weist darauf hin, dass es ein Lehrbuch der gleichen Autoren gibt, das eine etwas längere Liste enthält. Dies ist ein PDF des Buches. Die offenen Probleme beginnen auf Seite 237.

cc.complexity-theory open-problem circuit-complexity Robin Kothari
quelle
@ Robin, bitte CW.
Mohammad Al-Turkistany
5
@turkistany: Da diese sehr ähnliche Frage ( cstheory.stackexchange.com/q/1265/206 ) nicht unbedingt als CW eingestuft wurde, bin ich mir nicht sicher, ob dies CWed sein sollte. Ich folge den FAQ-Richtlinien "Im Zweifelsfall keine CW-Frage markieren" und warte auf weitere Meinungen.
Robin Kothari
@ András: Danke. Ich werde es zu meinem Beitrag hinzufügen. Es sieht aus wie eine etwas längere Liste der gleichen Autoren.
Robin Kothari

Antworten:

12

Übrigens: Die Liste der bekannten CC-vollständigen Probleme ist seit beiden Versionen des Buches gewachsen. Siehe dieses Papier von Greenlaw und Kanlabutra.

Paul Beame
quelle