Klasy złożoności obwodów liniowych

Klasa to funkcje klasy obliczalne przez rodziny obwodów ograniczonego wielkości i głębokości . -hierarchy jest sumą tych klas.$\textrm{NC}^i$$n^{O(1)}$$O(\log^i(n))$$\textrm{NC}$

Czy jest jakieś badanie wariantu wielkości hierarchicznej tej hierarchii? Czy to rodziny obwodów ograniczonego wachlarza, głębokości polilogu i rozmiaru liniowego?

Wiem, że istnieje trochę pracy z ale nic więcej. że co najmniej jest nietrywialny, ponieważ zawiera zwykłe języki (a zatem niektóre -kompletne języki).$\textrm{AC}^0$$\textrm{NC}^1$$\textrm{NC}^1$

Z pracy Valianta [1, 2] wynika, że rozmiarze można symulować za pomocą obwodów o wielkości o głębokości 3 i nieograniczonych wentylatorach w.$\textrm{NC}^1$$2^{O(n / \log \log n)}$

Miłą prezentację tego wyniku można znaleźć w części 3 ankiety przeprowadzonej przez Violę [3].

[1] Leslie G. Valiant. Argumenty teoretyczne w postaci graficznej o złożoności niskiego poziomu . W: Matematyczne podstawy informatyki 1977. MFCS 1977. Wykład notatki z informatyki, tom 53. Springer, Berlin, Heidelberg.

[2] Leslie G. Valiant. Wykładnicze dolne granice dla ograniczonych obwodów monotonicznych . W: Materiały z piętnastego dorocznego sympozjum ACM na temat teorii obliczeń (STOC '83). ACM, Nowy Jork, Nowy Jork, USA, 110-117.

[3] Emanuele Viola. O mocy obliczeń na małej głębokości . Podstawy i trendy w informatyce teoretycznej, vol. 5, nr 1, s. 1–72, 2009.