УДК 511
Асимптотика конъюнкторной сложности самокорректирующихся схем для монотонных симметрических функций с порогом 2 / Т. И. Краснова. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2014. № 3. С. 50-54.
Для монотонных симметрических булевых функций f2n(x1,..., xn) = V1≤i<j≤n xi xj при растущем n установлена асимптотика Lk&(f2n) ∼ (k+2)n, где Lk&(f2n) - конъюнкторная сложность реализации функции f2n k-самокорректирующимися схемами из функциональных элементов в базисе B = {&, - }, вес надежного конъюнктора ≥ k+2.
Ключевые слова: схемы из функциональных элементов, монотонные симметрические булевы функции, конъюнкторная сложность, самокорректирующаяся схема.
Библиогр. 6.
