О сложности реализации функций $k$-значной логики схемами и формулами в функционально полных базисах

Изучаются алгоритмические проблемы, связанные с реализацией ограниченно-детерминированных функций (ОДФ) схемами и формулами минимальной сложности в произвольных автоматных базисах. Известна алгоритмическая неразрешимость задачи нахождения асимптотики функции Шеннона в случае полных базисов. Однако коэффициент в формуле для функции Шеннона можно найти с произвольной точностью. В работе доказана так называемая сильная алгоритмическая неразрешимость задачи нахождения асимптотики функции Шеннона в случае функционально полных базисов. Базис называется сф-эквивалентным, если в асимптотических формулах для функций Шеннона в классах схем и формул константы совпадают. В случае функционально полных базисов доказаны существование базисов, не являющихся сф-эквивалентными, и сильная алгоритмическая неразрешимость задачи распознавания сф-эквивалентности базиса. Библиогр. 6.