Изменение размера оптимальной схемы при переходе к другому базису — различия между версиями
Sementry (обсуждение | вклад) |
Sementry (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
==Теорема== | ==Теорема== | ||
| − | Для любых базисов <math>~B_1</math>, <math>~B_2</math> и функции <math>~f</math> верно равенство <math>~size_{B_2}(f) \leq C_{(B_1,\;B_2)}size_{B_1}(f)</math> | + | Для любых базисов <math>~B_1</math>, <math>~B_2</math> и функции <math>~f</math> верно равенство <math>~size_{B_2}(f) \leq C_{(B_1,\;B_2)}size_{B_1}(f)</math>, где константа <math>~C</math> зависит только от базисов <math>~B_1</math> и <math>~B_2</math>. |
==Доказательство== | ==Доказательство== | ||
Пусть базис <math>~B_2</math> состоит из функций <math>~g_1, g_2, ..., g_n</math>. Схемная сложность функции <math>~g_i</math> относительно базиса <math>~B_1</math> равна <math>~size_{B_1}(g_i)</math>(по определению схемной сложности). Иначе говоря, каждый функциональный элемент базиса <math>~B_2</math> можно собрать с помощью элементов из базиса <math>~B_1</math>, затратив на это не более чем <math>~size_{B_1}(g_i)</math> элементов. Тогда понятно, что в сумме мы затратим не более чем в <math>~C = \max_{i=1}^n size_{B_1}(g_i)</math> раз больше функциональных элементов, и <math>~C</math> зависит только от выбранных базисов. | Пусть базис <math>~B_2</math> состоит из функций <math>~g_1, g_2, ..., g_n</math>. Схемная сложность функции <math>~g_i</math> относительно базиса <math>~B_1</math> равна <math>~size_{B_1}(g_i)</math>(по определению схемной сложности). Иначе говоря, каждый функциональный элемент базиса <math>~B_2</math> можно собрать с помощью элементов из базиса <math>~B_1</math>, затратив на это не более чем <math>~size_{B_1}(g_i)</math> элементов. Тогда понятно, что в сумме мы затратим не более чем в <math>~C = \max_{i=1}^n size_{B_1}(g_i)</math> раз больше функциональных элементов, и <math>~C</math> зависит только от выбранных базисов. | ||
Версия 07:28, 15 октября 2010
Эта статья находится в разработке!
Определение
Схемная сложность функции относительно базиса (обозначается ) - это минимальное количество функциональных элементов из набора , необходимое для реализации функции в базисе .
Теорема
Для любых базисов , и функции верно равенство , где константа зависит только от базисов и .
Доказательство
Пусть базис состоит из функций . Схемная сложность функции относительно базиса равна (по определению схемной сложности). Иначе говоря, каждый функциональный элемент базиса можно собрать с помощью элементов из базиса , затратив на это не более чем элементов. Тогда понятно, что в сумме мы затратим не более чем в раз больше функциональных элементов, и зависит только от выбранных базисов.
