75
правок
Изменения
м
→Доказательство: небольшое пояснение
* '''Блок D''' {{---}} мультиплексор, получающий на вход все <tex>f(x_1, x_2, ..., x_k, \sigma_{k + 1}, \sigma_{k + 2}, ..., \sigma_n)</tex> и параметры функции <tex>x_{k + 1}, x_{k + 2}, ..., x_n</tex> в качестве двоичного представления числа. '''''Результат работы схемы''''' {{---}} вывод мультиплексора.
Положим <tex>s = [n - 2\log_2 n]</tex>; <tex>k = [\log_2 n]</tex>. Тогдачисло элементов в блоках
* <tex>L_A \sim 2^k \lesssim \frac{2^n}{n}</tex>
* <tex>L_B \leq (s - 1) \cdot (t(1) + t(2) + ... + t(p)) < sp \cdot 2^s = 2^{k + s} = \frac{2^n}{n}</tex>
