O Nelinejnoj Slozhnosti Monotonnoj Realizacii Odnogo Semejstva Bulevyh Summ


R.L. Šćepanov'c


Postroeno konkretnoe semejstvo $n$ bulevyh summ ot $n$ peremennyh, realizaciya kotoryh posredstvom shem v monotonnom bazise trebuet po poryadku ne menee $n^{3/2-\varepsilon}$ elementov, dlya lyubogo $\varepsilon>0$. Postroennyj primer otnositsya k poka ewe malen'komu chislu $(<10)$ nelinejnyh nizhnih ocenok monotonnoj slozhenosti. Ukazannoe semejstvo bulevyh summ opisyvaetsya ochen' prosto (v otlichie ot ranee izvestnyh primerov nelinejnoj slozhnosti monotonnoj realizacii) i estestvenno voznikaet pri realizacii raspoznavanii nekotoryh izobrazhenij.