Problèmes dans NC non connus pour résider dans NC2

Existe-t-il des problèmes intéressants dans mais non connus dans ? Dans l'article «Une taxonomie des problèmes avec les algorithmes parallèles rapides», Cook mentionne que MIS était connu pour être uniquement dans mais cela a depuis été ramené à . Je me demande s'il y a d'autres problèmes avec les algorithmes parallèles de profondeur de polylog où nous semblons être bloqués sur l'amélioration de la profondeur.N C 2 N C 5 N C $\mathsf{NC}$$\mathsf{NC^{2}}$$\mathsf{NC^{5}}$$\mathsf{NC^{2}}$

Pour affiner encore plus, y a-t-il des problèmes dans qui ne sont pas connus pour être dans ou ? A C 1 D E $\mathsf{NC^{2}}$$\mathsf{AC^{1}}$$\mathsf{DET}$

Avertissement: je ne suis pas un expert en algorithmes parallèles rapides, donc la probabilité d'avoir raté des résultats plus récents qui mettent les problèmes que je mentionne dans les niveaux inférieurs de la hiérarchie $\mathsf{NC}$ n'est pas négligeable. Si vous constatez que c'est le cas, dites-le moi et je mettrai à jour ma réponse.

• Le rapport Algorithmes parallèles pour la recherche en profondeur d'abord traite des algorithmes parallèles connus pour DFS sur différents types de graphiques. La liste donnée aux pages 9-10 indique plusieurs algorithmes en $\mathsf{NC} \setminus \mathsf{NC}_2$ , tels que DFS pour les graphes plans non orientés, ou en $\mathsf{RNC} \setminus \mathsf{RNC}_2$ , tels que DFS pour les graphes généraux non orientés.

• Avec une recherche rapide, je n'ai pas trouvé d'articles améliorant les algorithmes parallèles pour une interpolation polynomiale multivariée clairsemée sur des champs finis de cet article , qui est en $\mathsf{NC}_3$ . Cependant, plusieurs documents qui auraient pu être pertinents étaient derrière un mur payant.

• Le calcul de toutes les cliques maximales dans un graphique est en $\mathsf{NC} \setminus \mathsf{NC}_2$ lorsque le nombre de cliques maximales est polynomialement borné, selon cet article .

• Le problème de chemin maximal semble être en $\mathsf{NC}_5$ pour les graphes généraux (non orientés), je n'ai pas trouvé d'algorithmes parallèles plus rapides sans restrictions sur le graphe sous-jacent.

D'autres candidats potentiels pourraient inclure des algorithmes pour trouver des correspondances parfaites dans des types spécifiques de graphiques, ou des algorithmes pour trouver une couverture arborescente maximale dans des graphiques arbitraires (par exemple, cet article mentionne un algorithme de polytime aléatoire en temps parallèle $O(\log^6n)$ ). Cet article mentionne également la résolution de classes de problèmes CSP qui se posent dans l'application de vision par ordinateur, en temps parallèle $O(\log^3n)$ .