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

Поляризованная полиномиальная форма (ППФ) (по модулю $k$) – это сумма по модулю $k$ произведений переменных $x_1, \dots, x_n$ или их отрицаний Поста, причем число отрицаний каждой переменной определяется вектором поляризации этой ППФ. Длиной ППФ называется число ее попарно различных слагаемых. Длиной функции $k$-значной логики $f(x_1, \dots, x_n)$ в классе ППФ называется минимальная длина среди всех ППФ, реализующих эту функцию. В работе построена такая последовательность симметрических функций трехзначной логики $f_n(x_1, \dots, x_n)$, что длина каждой из функций $f_n$ в классе ППФ не меньше, чем $\lfloor 3^{n+1}/4 \rfloor$, где $\lfloor a \rfloor$ обозначает наибольшее целое число, не превосходящее число $a$. Сложностью системы ППФ, имеющих один и тот же вектор поляризации, называется число попарно различных слагаемых, встречающихся во всех этих ППФ. Сложностью $L_k^{\textrm{ППФ}}(F)$ системы $F = \{f_1, \dots, f_m\}$ функций $k$-значной логики, зависящих от переменных $x_1, \dots, x_n$, в классе ППФ называется минимальная сложность среди всех таких систем ППФ $\{p_1, \dots, p_m\}$, что все ППФ $p_1, \dots, p_m$ имеют один и тот же вектор поляризации, и ППФ $p_j$ реализует функцию $f_j$, $j = 1, \dots, m$. Пусть $L_k^{\textrm{ППФ}}(m, n) = \max\limits_{F}L_k^{\textrm{ППФ}}(F)$, где индекс $F$ пробегает по всем системам, содержащим $m$ функций $k$-значной логики, зависящих от переменных $x_1, \dots, x_n$. Понятно, что при простых $k$ верна оценка $L_k^{\textrm{ППФ}}(m, n) \le k^n$. В работе доказано, что $L_2^{\rm ППФ}(m, n) = 2^n$ и $L_3^{\textrm{ППФ}}(m, n) = 3^n$ для всех $m \ge 2$, $n = 1, 2, \dots$. Более того, доказано, что оценки остаются такими же, если рассматривать только системы симметрических функций.
Работа поддержана РФФИ, проекты 13–01–00684-а, 13–01–00958-а.