О сложности распознавания полноты систем функций в классе $P_3^*$

С использованием метода полилинейных форм доказано, что для распознавания полноты относительно суперпозициии системы функций $\{f_1,\dots,f_s\}$ в алгебре $P_3^*$ частичных трехзначных функций, заданных вектором значений, существует алгоритм с битовой сложностью $O(N^{\log_36}\log^2 N)$, где $N$ – суммарная длина векторов значений всех функций системы.
Библиогр. 7.