Изменение размера оптимальной схемы при переходе к другому базису

Эта статья находится в разработке!

Определение

Размер схемы - количество функциональных элементов, необходимое для построения этой схемы. Схемная сложность функции [math]f[/math] относительно базиса [math]B[/math](обозначается [math]size_B(f)[/math]) - минимальный размер схемы, вычисляющей функцию [math]f[/math], собранной из функциональных элементов, принадлежащих базису [math]B[/math].

Теорема

Для любых базисов [math]B_1[/math], [math]B_2[/math] и функции [math]f[/math] верно равенство [math]size_{B_1}(f) \leq C_{B_1\; B_2}size_{B_2}(f)[/math]

Доказательство

Пусть базис [math]B_2[/math] состоит из функций [math]g_1, g_2, ..., g_n[/math]. Схемная сложность функции g_i относительно базиса [math]B_1[/math] равна [math]size_{B_1}(g_i)[/math]. Иначе говоря, каждый функциональный элемент базиса [math]B_2[/math] мы собираем с помощью элементов из базиса [math]B_1[/math]. Тогда понятно, что в сумме мы затратим не более чем в [math]C = max{i}size_{B_1}(g_i)[/math] раз больше функциональных элементов, и [math]C[/math] зависит от выбранных базисов, но не зависит от формулы.