Komplexitätsklassen für lineare Schaltungen

Die Klasse ist die Klassenfunktion, die durch Schaltungsfamilien mit begrenztem Fan-In, Größe und Tiefe berechnet werden kann. Die -Hierarchie ist die Vereinigung dieser Klassen.$\textrm{NC}^i$$n^{O(1)}$$O(\log^i(n))$$\textrm{NC}$

Gibt es eine Studie über die lineare Größenvariante dieser Hierarchie? Das sind Schaltkreisfamilien mit begrenztem Fan-In, Polylog-Tiefe und linearer Größe?

Ich weiß, dass es einige Arbeiten mit linear- aber sonst nichts. dass mindestens linear- trivial ist, da es reguläre Sprachen enthält (und daher einige vollständige Sprachen).$\textrm{AC}^0$$\textrm{NC}^1$$\textrm{NC}^1$

Aus der Arbeit von Valiant [1, 2] folgt, dass mit linearer Größe durch Größe von simuliert werden kann. im.$\textrm{NC}^1$$2^{O(n / \log \log n)}$

Eine schöne Darstellung dieses Ergebnisses finden Sie in Abschnitt 3 der Umfrage von Viola [3].

[1] Leslie G. Valiant. Graphentheoretische Argumente in geringer Komplexität . In: Mathematische Grundlagen der Informatik 1977. MFCS 1977. Lecture Notes in Computer Science, Band 53. Springer, Berlin, Heidelberg.

[2] Leslie G. Valiant. Exponentielle Untergrenzen für eingeschränkte monotone Schaltkreise . In: Vorträge des fünfzehnten jährlichen ACM-Symposiums zur Theorie des Rechnens (STOC '83). ACM, New York, NY, USA, 110-117.

[3] Emanuele Viola. Über die Leistung der Berechnung mit geringer Tiefe . Grundlagen und Trends der Theoretischen Informatik, vol. 5, num. 1, S. 1–72, 2009.