308
правок
Изменения
Добавлено про глубину
Пусть базис <tex>~B_2</tex> состоит из функций <tex>~g_1, g_2, ..., g_n</tex>. Каждый функциональный элемент базиса <tex>~B_2</tex> можно собрать с помощью элементов не более чем <tex>~size_{B_1}(g_i)</tex> элементов из базиса <tex>~B_1</tex>. Собрать <tex>f</tex> в базисе <tex>B_1</tex> можно следующим образом: заменить каждый элемент схемы <tex>f</tex> в базисе <tex>B_2</tex> на схему соответствующей функции в базисе <tex>B_1</tex>. Такая сборка использует не более чем в <tex>~C = \max_{i=1}^n size_{B_1}(g_i)</tex> раз больше функциональных элементов, чем соответствующая схема в <tex>B_2</tex>. Параметр <tex>~C</tex> зависит только от выбранных базисов.
}}
== Глубина схемы ==
{{Определение
|definition= '''Глубина схемы''' для функции <tex>f</tex> относительно базиса <tex>B</tex> — это максимальная длина пути от входа до выхода по схеме соответствующей функции <tex>f</tex>, состоящей из элементов набора <tex>B</tex>, где за единицу длины принимается один элемент схемы.
Глубину схемы для функции <tex>f</tex> в базисе <tex>B</tex> обозначают <tex>depth_B(f)</tex>
}}
Примечание: понятие глубины имеет смысл только для схем с ограниченной степенью входа (''bounded fan-in'').
{{Теорема
|about=аналогична теореме про схемную сложность
|statement =
Для любых базисов <tex>~B_1</tex>, <tex>~B_2</tex> и функции <tex>~f</tex> верно неравенство <tex>~depth_{B_2}(f) \leq C_{(B_1,\;B_2)}depth_{B_1}(f)</tex>, где константа <tex>~C</tex> зависит только от базисов <tex>~B_1</tex> и <tex>~B_2</tex>.
}}
Доказательство в точности повторяет доказательство предыдущей теоремы.
== Источники ==
