20
правок
Изменения
→Теорема о нижней оценке на число элементов в схеме
'''Длина''' линейной программы {{---}} количество строк.
{{Теорема
|statement= Для булевой функции <tex>f \; \exists</tex> существует линейная программа длины <tex>r \Leftrightarrow \exists </tex> тогда и только тогда, когда существует схема, использующая <tex>r</tex> функциональных элементов.
|proof=Чтобы построить по схеме программу, можно занумеровать элементы схемы в порядке [[Использование_обхода_в_глубину_для_топологической_сортировки#Топологическая_сортировка|топологической сортировки]], и для каждого элемента <tex>m</tex> с функцией <tex>a</tex> и входами <tex>i_1, \ldots, i_k</tex> сопоставить строчку линейной программы с номером <tex>m</tex> вида <tex>(a, (i_1, \ldots, i_k))</tex>.
{{Лемма
|id=Лемма1
|statement=<tex>\exists</tex> Существует булева функция <tex>f: size_B(f) \geq \frac{2^n}{2n}</tex>
|proof=Посчитаем число линейных программ длиной <tex>r < \frac{2^n}{2n} </tex>
