Изменения

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

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

==ТеоремаСм. также==Для любых базисов <math>B1</math>, <math>B2</math> и [[Реализация булевой функции <math>f</math> <math>SIZEb1(f)</math> = <math>O(SIZEb2(f))</math> ==Доказательство==схемой из функциональных элементов]]