RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Московского университета. Серия 1: Математика. Механика // Архив

Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2014, номер 3, страницы 50–54 (Mi vmumm322)

Эта публикация цитируется в 2 статьях

Краткие сообщения

Асимптотика конъюнкторной сложности самокорректирующихся схем для монотонных симметрических функций с порогом $2$

Т. И. Краснова

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Для монотонных симметрических булевых функций $f_2^n(x_1,\ldots,x_n)=\bigvee \limits_{1\leq i<j\leq n}x_i x_j$ при растущем $n$ установлена асимптотика $L_k^{\&}(f^n_2)\thicksim (k+2)n,$ где $L_k^{\&}(f^n_2)$ — конъюнкторная сложность реализации функции $f^n_2$ $k$-самокорректирующимися схемами из функциональных элементов в базисе $B=\{\&,-\}$, вес надежного конъюнктора $\geq k+2$.

Ключевые слова: схемы из функциональных элементов, монотонные симметрические булевы функции, конъюнкторная сложность, самокорректирующаяся схема.

УДК: 511

Поступила в редакцию: 13.04.2012


 Англоязычная версия: Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2014, 69:3, 121–124

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


© МИАН, 2024