Проблемы в NC не известны в NC2

Есть ли интересные проблемы, которые есть в но неизвестно, что они есть в ? В статье «Таксономия проблем с быстрыми параллельными алгоритмами» Кук упоминает, что MIS, как было известно, находится только в но с тех пор он был переведен в , Мне интересно, есть ли какие-либо другие проблемы с параллельными алгоритмами глубины полилога, где мы, кажется, застряли в улучшении глубины.$\mathsf{NC}$$\mathsf{NC^{2}}$$\mathsf{NC^{5}}$$\mathsf{NC^{2}}$

Чтобы сузить еще больше, есть ли проблемы в которые, как известно, не находятся в или ?$\mathsf{NC^{2}}$$\mathsf{AC^{1}}$$\mathsf{DET}$

Отказ от ответственности: я не эксперт в быстрых параллельных алгоритмах, поэтому вероятность того, что я пропустил более поздние результаты, которые ставят проблемы, о которых я упоминаю, на более низких уровнях иерархии ничтожна. Если вы заметили, что это так, пожалуйста, сообщите мне, и я обновлю свой ответ.$\mathsf{NC}$

• В отчете « Параллельные алгоритмы для поиска в глубину» обсуждаются известные параллельные алгоритмы для DFS на различных типах графиков. Список, приведенный на страницах 9-10, указывает на несколько алгоритмов в , таких как DFS для плоских неориентированных графов, или в , такие как DFS для общих неориентированных графов.$\mathsf{NC} \setminus \mathsf{NC}_2$$\mathsf{RNC} \setminus \mathsf{RNC}_2$

• При быстром поиске я не смог найти работ, улучшающих параллельные алгоритмы для разреженной многомерной полиномиальной интерполяции над конечными полями этой статьи , которая находится в . Тем не менее, несколько документов, которые могли бы иметь отношение к делу, находились за платным доступом.$\mathsf{NC}_3$

• Согласно этой статье, вычисление всех максимальных кликов в графе происходит в когда число максимальных клик ограничено полиномиально .$\mathsf{NC} \setminus \mathsf{NC}_2$

• Кажется, проблема максимального пути в$\mathsf{NC}_5$ для общих (неориентированных) графов, я не нашел более быстрых параллельных алгоритмов без ограничений на основной граф.

Другие потенциальные кандидаты могут включать в себя алгоритмы для нахождения идеальных совпадений в определенных типах графов или алгоритмы для нахождения максимального покрытия дерева в произвольных графах (например, в этой статье упоминаются рандомизированные алгоритмы множителя в параллельном времени ). В этой статье также упоминается решение классов задач CSP, возникающих в приложении для компьютерного зрения, параллельно .$O(\log^6n)$$O(\log^3n)$