Архив статей

СЛОЖНОСТЬ ПРОИЗВОЛЬНЫХ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ МАЛОГО ЧИСЛА ПЕРЕМЕННЫХ (2022)
Выпуск: Т. 65 № 7 (2022)

Рассмотрен способ оценивания сложности произвольных функций алгебры логики, основанный на их представлении композицией монотонных функций. Получены точные верхние оценки сложности монотонных и произвольных функций, зависящих от малого числа переменных.