Теорема Шеннона — Лупанова

1. Для любого базиса ${\displaystyle \Sigma }$ : ${\displaystyle L_{\Sigma }(n)\sim C_{\Sigma }{\frac {2^{n}}{n}}}$ , где ${\displaystyle C_{\Sigma }}$  — константа, зависящая от базиса.

2. Для любого ${\displaystyle \epsilon >0}$  доля функций ${\displaystyle f}$ , для которых ${\displaystyle L_{\Sigma }(f)\leqslant (1-\epsilon )C_{\Sigma }{\frac {2^{n}}{n}}}$  стремится к нулю с ростом ${\displaystyle n}$ .

Здесь ${\displaystyle L_{\Sigma }(n)=\max _{f\in P(n)}L_{\Sigma }(f)}$ , где максимум берется по всем функциям от ${\displaystyle n}$  переменных^{[прояснить]}. Знак ${\displaystyle \sim }$  обозначает асимптотическое равенство: ${\displaystyle a(n)\sim b(n)}$ , если ${\displaystyle \lim _{n\to \infty }{\frac {a(n)}{b(n)}}=1}$ . Смысл второго утверждения теоремы в том, что с ростом ${\displaystyle n}$  почти все функции реализуются со сложностью, близкой к верхней границе ${\displaystyle L(n)}$ .

Доказательство есть в статье^[1].

• Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: Энергоатомиздат, 1988. — 480 с. — ISBN 5-283-01563-7.