689
правок
Изменения
Нет описания правки
==Определение==
Размер схемы - количество функциональных элементов, необходимое для построения этой схемы.
Схемная сложность функции <math>f</math> относительно базиса <math>B</math>(обозначается <math>SIZEbsize_B(f)</math>) - минимальный размер схемы, вычисляющей функцию <math>f</math>, собранной из функциональных элементов, принадлежащих базису <math>B</math>.
==Теорема==
Для любых базисов <math>B_1</math>, <math>B_2</math> и функции <math>f</math> верно равенство <math>SIZE_size_{B_1}(f)</math> = <math>O(SIZE_\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> зависит от выбранных базисов, но не зависит от формулы.
