О сложности ориентированных контактных схем с ограниченной полустепенью исхода

В работе исследуется реализация булевых функций в классе ориентированных контактных схем (ОКС) с некоторыми ограничениями на вес и число смежных контактов. Рассматриваются ОКС, в которых из произвольной вершины может исходить не более $\lambda$ дуг. Вводится понятие веса вершины ОКС, который полагается равным $\lambda$, если в вершину входит одна дуга и $\lambda(1+\omega)$, где $\omega>0$, в противном случае. Далее обычным образом определяется вес ОКС как сумма весов вершин, вес булевой функции как минимальный вес реализующих ее ОКС и функция Шеннона $W_{\lambda,\omega}(n)$ как максимальный вес булевой функции от $n$ переменных. Для этой функции Шеннона при $\lambda>1$ и произвольном $\omega>0$ получена так называемая оценка высокой степени точности:
$$ W_{\lambda,\omega}(n)=\frac\lambda{\lambda-1}\frac{2^n}n\Biggl(1+\frac{\frac{\lambda-2}{\lambda-1}\log n\pm O(1)}n\Biggr). $$

Полученный результат показывает, каким образом введение ограничений на количество исходящих из вершин ОКС дуг влияет на асимптотическое поведение функции Шеннона $W_{\lambda,\omega}(n)$ и на первый остаточный член ее разложения. Отметим, что от величины $\omega$ зависит только константа в члене $O(1)$.