Kelas kompleksitas sirkuit linear

Kelas $\textrm{NC}^i$ adalah fungsi kelas yang dapat dihitung oleh rangkaian keluarga dengan ukuran kipas masuk, $n^{O(1)}$ dan kedalaman $O(\log^i(n))$ . The $\textrm{NC}$ -hierarchy adalah gabungan dari kelas-kelas.

Apakah ada studi varian ukuran linear dari hierarki ini? Itu adalah keluarga rangkaian fan-in terbatas, kedalaman polylog dan ukuran linier?

Saya tahu mereka ada beberapa pekerjaan dengan $\textrm{AC}^0$ linear 0 tetapi tidak ada yang lain. Perhatikan bahwa paling tidak linear - $\textrm{NC}^1$ adalah non-trivial karena mengandung bahasa reguler (dan dengan demikian beberapa bahasa $\textrm{NC}^1$ -lengkap).

$\textrm{NC}^1$$2^{O(n / \log \log n)}$

Untuk penjelasan yang bagus tentang hasil ini, lihat bagian 3 survei oleh Viola [3].

[1] Leslie G. Valiant. Argumen grafik-teoretis dalam kompleksitas tingkat rendah . Dalam: Yayasan Matematika Ilmu Komputer 1977. MFCS 1977. Catatan Kuliah dalam Ilmu Komputer, vol 53. Springer, Berlin, Heidelberg.

[2] Leslie G. Valiant. Batas bawah eksponensial untuk sirkuit monoton terbatas . Dalam: Prosiding simposium ACM tahunan kelima belas tentang Teori komputasi (STOC '83). ACM, New York, NY, AS, 110-117.

[3] Emanuele Viola. Pada kekuatan perhitungan kedalaman kecil . Yayasan dan Tren dalam Ilmu Komputer Teoritis, vol. 5, num. 1, hlm. 1--72, 2009.