Документ взят из кэша поисковой машины. Адрес оригинального документа : http://vestnik.math.msu.su/ru/DATA/2001/6/node3
Дата изменения: Unknown
Дата индексирования: Sun Apr 10 22:28:37 2016
Кодировка: Windows-1251
Вестник МГУ. Математика. Механика
Вестник Московского Университета. Математика, Механика - Содержание


УДК 519.6

О реализации линейной функции формулами в различных базисах / Черухин Д.Ю. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2001. N.6 C. 15-19.

Исследуется сложность реализации линейной булевой функции $ x_1\oplus x_2\oplus\ldots\oplus x_n $ формулами в различных базисах. Все базисы удалось разбить на три типа: в базисах первого типа сложность линейной функции по порядку равна $ n^2 $; в базисах второго -- по порядку не меньше, чем $ n^\beta $, и не больше, чем $ n^\gamma $, где $ 1<\beta<\gamma<2 $ (константы $ \beta $ и $ \gamma $ вычисляются по базису); в базисах третьего типа по порядку равна $n$.

Библиогр. 8.

К оглавлению номера  Go!