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

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

Определение

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

Теорема

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

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

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