Analog eksponensial dari NC?

Nick's Class (NC) adalah kelas masalah yang dapat diputuskan dalam waktu poly-log menggunakan sejumlah prosesor polinomial.

Saya ingin tahu tentang analog eksponensial, yang akan mencakup masalah yang dapat diputuskan dalam waktu polinomial menggunakan jumlah prosesor yang eksponensial.

Apa yang saya cari adalah nama untuk kelas ini dan hubungan yang diketahui antara kelas ini dan kelas kompleksitas lainnya, atau masalah kanonik untuk kelas tersebut. Tampaknya langsung bahwa itu akan mengandung NP dan co-NP, dan saya pikir itu terkandung dalam PSPACE, tapi saya tidak yakin banyak tentang hal itu.

Waktu dalam sirkuit sesuai dengan kedalaman. Oleh karena itu waktu polinomial berarti kedalaman polinomial.

Jumlah prosesor adalah ukuran sirkuit, yaitu jumlah gerbang di sirkuit. Jadi dengan jumlah prosesor yang eksponensial, Anda mengizinkan ukuran eksponensial. Ini akan menjadi kelas . Tetapi setiap fungsi sudah masuk$\mathsf{DepthSize}(n^{O(1)}, 2^{n^{O(1)}})$$\mathsf{DepthSize}(2, 2^{n^{O(1)}})$ (pikirkan CNF dari fungsi yang ingin Anda hitung).

Kesimpulannya adalah bahwa jumlah prosesor yang eksponensial terlalu kuat untuk berguna dengan sendirinya.

Satu batasan yang masuk akal untuk membatasi jumlah komunikasi antara proses yang berbeda. Misalnya kita setiap proses hanya dapat berkomunikasi dengan banyak proses lainnya secara polinomi dan pesan memiliki ukuran polinomial. Itu akan menjadi$\mathsf{PSpace}$seperti yang dijelaskan dalam jawaban atas pertanyaan Aterm tentang sejarah . Cara lain melihatnya untuk mengingatnya $\mathsf{PSpace} = \mathsf{ATime}(n^{O(1)})$, masalah yang dapat dihitung dengan mengganti mesin Turing dalam waktu polinomial. Alternatif dalam mesin Turing pada dasarnya forking proses baru dan kemudian bergabung setelah mereka selesai dengan mengambil konjungsi / disjungsi dari nilai kembali mereka.