Masalah di NC tidak diketahui terletak di NC2

Apakah ada masalah menarik yang ada di tetapi tidak diketahui berada di N C 2 ? Dalam tulisan 'A Taksonomi Masalah Dengan Cepat Paralel Algoritma', Masak menyebutkan bahwa MIS dikenal hanya berada di N C 5 tapi ini sejak itu telah dibawa ke N C 2 . Saya bertanya-tanya apakah ada masalah lain dengan algoritma paralel polylog-depth di mana kita tampaknya terjebak pada peningkatan kedalaman.$\mathsf{NC}$$\mathsf{NC^{2}}$$\mathsf{NC^{5}}$$\mathsf{NC^{2}}$

Untuk mempersempit lebih jauh, apakah ada masalah dalam yang tidak diketahui berada di A C 1 atau D E T ?$\mathsf{NC^{2}}$$\mathsf{AC^{1}}$$\mathsf{DET}$

Disclaimer: Saya bukan ahli dalam algoritma paralel cepat, maka probabilitas bahwa aku merindukan hasil yang lebih baru yang menempatkan masalah yang saya sebutkan di tingkat yang lebih rendah dari $\mathsf{NC}$ hirarki adalah non-diabaikan. Jika Anda perhatikan bahwa ini masalahnya, beri tahu saya dan saya akan memperbarui jawaban saya.

• Laporan Algoritma Paralel untuk Kedalaman-Pencarian Pertama membahas algoritma paralel yang dikenal untuk DFS pada berbagai jenis grafik. Daftar yang diberikan pada halaman 9-10 menunjukkan beberapa algoritma dalam $\mathsf{NC} \setminus \mathsf{NC}_2$ , seperti DFS untuk grafik tak berarah planar, atau dalam $\mathsf{RNC} \setminus \mathsf{RNC}_2$ , seperti DFS untuk grafik tak berarah umum.

• Dengan pencarian cepat, saya tidak dapat menemukan makalah yang meningkat melalui algoritma paralel untuk interpolasi polinomial multivariat yang jarang di atas bidang terbatas dari makalah ini , yang ada di $\mathsf{NC}_3$ . Namun, beberapa makalah yang mungkin relevan ada di balik paywall.

• Komputasi semua klik maksimum dalam grafik adalah dalam $\mathsf{NC} \setminus \mathsf{NC}_2$ ketika jumlah klik maksimal dibatasi secara polinomial, menurut makalah ini .

• Masalah jalur maksimal tampaknya berada di $\mathsf{NC}_5$ untuk grafik umum (tidak terarah), saya belum menemukan algoritma paralel yang lebih cepat tanpa batasan pada grafik yang mendasarinya.

Kandidat potensial lainnya mungkin termasuk algoritma untuk menemukan kecocokan sempurna dalam jenis grafik tertentu, atau algoritma untuk menemukan tutupan pohon maksimal dalam grafik arbitrer (misalnya makalah ini menyebutkan algoritma polytime acak dalam waktu paralel $O(\log^6n)$ ). Makalah ini juga menyebutkan pemecahan kelas masalah CSP yang muncul dalam aplikasi visi komputer, dalam waktu paralel $O(\log^3n)$ .