УДК 519.6
О сложностной иерархии булевых базисов / Черухин Д.Ю. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика.
C. 48-50.
Исследуется зависимость сложности булевых функций в классе формул от функционального базиса. В связи с этим на множестве базисов вводится отношение частичного порядка (как это было сделано в работах Б.А. Субботовской, В.А. Стеценко и автора). Основным результатом работы является критерий, позволяющий устанавливать выполнимость этого отношения для произвольных базисов.
Библиогр. 4.
