Изменения

{{В разработкеОпределение|definition ='''Схемная сложность''' функции <tex>~f</tex> относительно базиса <tex>~B</tex>(обозначается <tex>~size_B(f)</tex>) - это минимальное количество функциональных элементов из набора <tex>~B</tex>, необходимое для реализации функции <tex>~f</tex> в базисе <tex>~B</tex>.}}

==Определение==Схемная сложность функции <math>~f</math> относительно базиса <math>~B</math>(обозначается <math>~size_B(f)</math>) - это минимальное количество функциональных элементов из набора <math>~B</math>, необходимое для реализации функции <math>~f</math> в базисе <math>~B</math>.{{Теорема==Теорема=|statement =Для любых базисов <mathtex>~B_1</mathtex>, <mathtex>~B_2</mathtex> и функции <mathtex>~f</mathtex> верно равенство неравенство <mathtex>~size_{B_2}(f) \leq C_{(B_1,\;B_2)}size_{B_1}(f)</mathtex>, где константа <mathtex>~C</mathtex> зависит только от базисов <mathtex>~B_1</mathtex> и <mathtex>~B_2</mathtex>. ==Доказательство=|proof =Пусть базис <mathtex>~B_2</mathtex> состоит из функций <mathtex>~g_1, g_2, ..., g_n</mathtex>. Схемная сложность функции <mathtex>~g_i</mathtex> относительно базиса <mathtex>~B_1</mathtex> равна <mathtex>~size_{B_1}(g_i)</mathtex>(по определению схемной сложности). Иначе говоря, каждый функциональный элемент базиса <mathtex>~B_2</mathtex> можно собрать с помощью элементов из базиса <mathtex>~B_1</mathtex>, затратив на это не более чем <mathtex>~size_{B_1}(g_i)</mathtex> элементов. Тогда понятно, что Поэтому в сумме мы затратим не более чем в <mathtex>~C = \max_{i=1}^n size_{B_1}(g_i)</mathtex> раз больше функциональных элементов, и <mathtex>~C</mathtex> зависит только от выбранных базисов.}}