Том 5, серия 1, номер 2, 1998 г., Стр. 78-89

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

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

Орлов В. А. ¹
1. Российский государственный гуманитарный университет,
111116 Москва, Россия
е-mail: orloval@rsuh.ru

Статья поступила 30 ноября 1997 г.