УДК 519.95
Доказательство нижних оценок сложности самокорректирующихся схем методом замены базиса / Н. П. Редькин // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2010. № 3. С. 14-18.
В статье представлен метод получения новых нижних оценок сложности реализации индивидуальных булевых функций, основанный на переходе от рассматриваемого базиса к другому базису, для которого уже известны хорошие нижние оценки сложности данных функций. Эффективное использование этого метода демонстрируется на примере получения асимптотики для сложности реализации пороговых функций самокорректирующимися схемами из многовходовых элементов.
Ключевые слова: булевы функции, самокорректирующиеся схемы, сложность реализации функций.
Библиогр. 7.
