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

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!

Определение

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

Теорема

Для любых базисов [math]B_1[/math], [math]B_2[/math] и функции [math]f[/math] [math]SIZE_{B_1}(f)[/math] = [math]O(SIZE_{B_2}(f))[/math]

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