Вестник Московского Университета. Математика, Механика - Содержание


УДК 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!