Сложность многослойных $d$-мерных схем

В данной работе рассматривается модель многослойных схем с одним функциональным слоем. В качестве графов-носителей выступают $\lambda $-сепарируемые графы. Доказана нижняя оценка функции Шеннона для сложности данного вида схем $ \max \left(\frac{2^n}{n}, \frac{2^n (1 - \lambda)}{\log k} \right)$, где k - число слоев. Для $d$-мерных графов, которые являются частным случаем $ \lambda $-сепарируемых графов для $ \lambda $ = $ \frac{d - 1}{d} $, таким образом получена нижняя оценка функции Шеннона $ \frac{2^n}{\min(n, d \log k)} $. Для прямоугольных многомерных схем доказанная нижняя оценка асимптотически совпадает с верхней оценкой.