Probleme in NC sind in NC2 nicht bekannt

Gibt es interessante Probleme in jedoch nicht bekannt ist, dass sie in N C 2 sind ? In der Arbeit 'Eine Taxonomie der Probleme mit schnellen parallelen Algorithmen' erwähnt Cook, dass MIS bekanntermaßen nur in N C 5 vorkommt , dies jedoch inzwischen auf N C 2 reduziert wurde . Ich frage mich, ob es bei parallelen Algorithmen mit Polylog-Tiefe noch andere Probleme gibt, bei denen wir anscheinend nicht weiterkommen, um die Tiefe zu verbessern.$\mathsf{NC}$$\mathsf{NC^{2}}$$\mathsf{NC^{5}}$$\mathsf{NC^{2}}$

Noch weiter eingrenzen: Gibt es Probleme in , von denen nicht bekannt ist, dass sie sich in A C 1 oder D E T befinden ?$\mathsf{NC^{2}}$$\mathsf{AC^{1}}$$\mathsf{DET}$

Disclaimer: Ich bin kein Experte in schnelle parallele Algorithmen, also die Wahrscheinlichkeit , dass ich aktuellere Ergebnisse verpasst, die die Probleme , die ich in den unteren Ebenen des Hinweises setzen $\mathsf{NC}$ - Hierarchie ist nicht zu vernachlässigen. Wenn Sie feststellen, dass dies der Fall ist, teilen Sie mir dies bitte mit, und ich werde meine Antwort aktualisieren.

• In dem Bericht Parallele Algorithmen für die Tiefensuche werden bekannte parallele Algorithmen für DFS für verschiedene Arten von Diagrammen erörtert. Die Liste auf den Seiten 9 bis 10 gibt verschiedene Algorithmen in $\mathsf{NC} \setminus \mathsf{NC}_2$ , z. B. DFS für planare ungerichtete Diagramme oder in $\mathsf{RNC} \setminus \mathsf{RNC}_2$ , z. B. DFS für allgemeine ungerichtete Diagramme.

• Bei einer schnellen Suche konnte ich keine Arbeiten finden, die sich gegenüber den parallelen Algorithmen für die spärliche multivariate Polynominterpolation über endliche Felder in dieser Arbeit in $\mathsf{NC}_3$ verbessern . Hinter einer Paywall steckten jedoch einige Papiere, die möglicherweise relevant gewesen sein könnten.

• Die Berechnung aller maximalen Cliquen in einem Graphen erfolgt in $\mathsf{NC} \setminus \mathsf{NC}_2$ wenn die Anzahl der maximalen Cliquen gemäß dieser Veröffentlichung polynomiell begrenzt ist .

• Das Problem mit dem maximalen Pfad scheint in $\mathsf{NC}_5$ für allgemeine (ungerichtete) Graphen zu liegen. Ich habe keinen schnelleren parallelen Algorithmus gefunden, der den zugrunde liegenden Graphen nicht einschränkt.

Andere potenzielle Kandidaten könnten Algorithmen zum Auffinden perfekter Übereinstimmungen in bestimmten Arten von Graphen oder Algorithmen zum Auffinden einer maximalen Baumbedeckung in beliebigen Graphen umfassen (z. B. erwähnt dieser Aufsatz einen randomisierten Polyzeit-Algorithmus in paralleler Zeit $O(\log^6n)$ ). In diesem Artikel wird auch das Lösen von CSP-Problemklassen erwähnt, die bei der Anwendung von Computer Vision in der Parallelzeit $O(\log^3n)$ .