УДК 511

Асимптотика конъюнкторной сложности самокорректирующихся схем для монотонных симметрических функций с порогом 2 / Т. И. Краснова. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2014. № 3. С. 50-54.

Для монотонных симметрических булевых функций f₂ⁿ(x₁,..., x_n) = V_1≤i<j≤n x_i x_j при растущем n установлена асимптотика L_k^&(f₂ⁿ) ∼ (k+2)n, где L_k^&(f₂ⁿ) - конъюнкторная сложность реализации функции f₂ⁿ k-самокорректирующимися схемами из функциональных элементов в базисе B = {&, - }, вес надежного конъюнктора ≥ k+2.

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

Библиогр. 6.