Lepsze dolne granice niż 3n dla funkcji innych niż boolowskie?

Dolna granica Bluma jest najlepiej znaną dolną granicą obwodu w całej bazie dla jawnej funkcji f : { 0 , 1 } n → { 0 , 1 } , por. Odpowiedź Jukny na to pytanie zawiera powiązane wyniki.$3n-o(n)$$f : \{0,1\}^n \to \{0,1\}$

Jakie są najbardziej znane dolne granice, jeśli zakres wynosi { 0 , 1 } m ? W szczególności, czy otrzymujemy coś lepszego dla m = n , czy dla m = 2 ?$f$$\{0,1\}^m$$m = n$$m = 2$

Zgodnie z artykułem A Dolna$5n − o(n)$$U_2$ granica wielkości obwodu nad U 2 liniowej funkcji boolowskiej autorstwa Kulikova, Melanicha i Mihajlina, gdy nie ma znanych dolnych granic lepszych niż 3 n - o ( n ) . Przedstawia także metodę uzyskiwania funkcji, dla których obowiązuje dolna granica 4 n - o ( n ) , gdy m = $m=o(n)$$3n - o(n)$$4n - o(n)$$m=n$, na podstawie wyników Lamagne i Savage.

tutaj są nowe wyniki na ten temat mówi się, że 1 ^st w ~ 3 lat, a niektóre krótki komentarz

• Lepsza niż -3n dolna granica złożoności obwodu jawnej funkcji / Find, Golovnev, Hirsch, Kulikov

  Obwody logiczne traktujemy w oparciu o pełną bazę binarną. Udowadniamy dolna granica wielkości takiego obwodu dla wyraźnie określonego predykatu, a mianowicie afinicznego dyspergatora dla wymiaru podliniowego. Poprawia to granicę3n-o(n)Norberta Bluma (1984).$(3+\frac{1}{86})n−o(n)$$3n−o(n)$

• Dolne granice lepszego obwodu dla jawnych funkcji / Ilya Razenshteyn, blog studencki MIT CSAIL