RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2008, том 20, выпуск 1, страницы 120–130 (Mi dm995)

О сложности реализации одного класса почти симметрических функций формулами глубины 3

С. Е. Черухина


Аннотация: В работе рассматривается класс почти симметрических булевых функций. Для любой функции из этого класса значения на любом слое, кроме второго, совпадают со значениями монотонной симметрической функции с порогом 3. Значения на втором слое произвольны. Изучается реализация функций из этого класса $\&\vee\&$-формулами в базисе $\{\&,\vee\}$.
Получены точная оценка минимальной сложности функций данного класса (функция минимальной сложности указана явно) и асимптотически точная оценка сложности монотонной симметрической функции с порогом 3, максимальной по порядку сложности в исследуемом классе.

УДК: 519.7

Статья поступила: 19.12.2005

DOI: 10.4213/dm995


 Англоязычная версия: Discrete Mathematics and Applications, 2008, 18:2, 131–142

Реферативные базы данных:


© МИАН, 2024