Теорема о нижней оценке на число элементов в схеме
| Теорема: |
Большинство булевых функций требуют для реализации порядка [math]\Omega(\frac{2^n}{n})[/math] функциональных элементов, где [math]n[/math] — количество аргументов функции.
Формальная запись теоремы:
[math]f(n) = \frac{2^n}{n} \; \; \; g(n): \frac{g}{f} \longrightarrow 0[/math]
[math]F_g = \{\text{Булевы функции, } size \leq g(n)\}[/math]
Тогда [math]\frac{|F_g|}{2^{2^n}} \longrightarrow 0[/math] |
Для доказательства этой теоремы нам понадобится доказать несколько вспомогательных утверждений.
| Определение: |
| Линейная программа — список строк вида [math](a, (i_1, \ldots, i_k))[/math], где [math]a \in B[/math] (базис), [math]a: \mathbb B^k \rightarrow \mathbb B[/math], [math]i_j[/math] — индексы переменных. |
Пример линейной программы
Линейная программа для функции [math]x_1 \oplus x_2[/math] над базисом [math]\{ \land, \lor, \lnot \}[/math]
[math]y_1 = \lnot x_1[/math]
[math]y_2 = \lnot x_2[/math]
[math]y_3 = x_1 \land y_2[/math]
[math]y_4 = x_2 \land y_1[/math]
[math]y_5 = y_3 \lor y_4[/math]
Длина линейной программы — количество строк.
| Теорема: |
Для булевой функции [math]f \; \exists[/math] линейная программа длины [math]r \Leftrightarrow \exists [/math] схема, использующая [math]r[/math] функциональных элементов. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке топологической сортировки, и для каждого элемента [math]m[/math] с функцией [math]a[/math] и входами [math]i_1, \ldots, i_k[/math] сопоставить строчку линейной программы с номером [math]m[/math] вида [math](a, (i_1, \ldots, i_k))[/math].
Построение функциональной схемы по линейной программе очевидно. |
| [math]\triangleleft[/math] |
Оценка на количество линейных программ над [math]\{\downarrow\}[/math] длины [math]r[/math]
[math]n[/math] — количество аргументов булевой функции.
Количество линейных программ [math]= K_{n, r} = n^2 \cdot (n+1)^2 \cdot (n+2)^2 \cdot \ldots \cdot (n+r-1)^2 \leq (n+r)^{2r}[/math]
[math]\log_2{K_{n, r}} \leq \log_2 {(n+r)^{2r}} = 2r \log_2 {(n+r)}[/math]
| Лемма: |
[math]\exists[/math] булева функция [math]f: size_B(f) \geq \frac{2^n}{2n}[/math] |
| Доказательство: |
| [math]\triangleright[/math] |
|
Предположим противное, пусть размер всех линейных программ [math]r \lt \frac{2^n}{2n} [/math]
[math]\log_2{K_{n, r}} \leq 2 r \log_2 {(n+r)} \lt \frac{2 \cdot 2^n}{2n} \log_2{(n+ \frac{2^n}{2n})} \leq \frac{2^n}{n} \log_2 {2^n} = 2^n \Rightarrow[/math]
[math]K_{n, r} \lt 2^{2^n}[/math] — такого быть не может, следовательно, [math]\exists \; f_n: r\gt \frac{2^n}{2n} [/math]
Обобщим для произвольного [math]c[/math]
[math]r\lt \frac{2^n}{2cn}[/math]
[math]\log_2 K_{n,r}\leq 2r\log_2(n+r)\lt \frac{2\cdot 2^n}{2cn}\log_2(n+\frac{2^n}{2cn})\leq \frac{2^n}{cn}\log_2 2^n=\frac{2^n}{c} \Rightarrow[/math]
[math]K_{n,r}\lt 2^{\frac{2^n}{c}} !!! [/math] |
| [math]\triangleleft[/math] |
