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

Поляризованная полиномиальная форма (ППФ) (по модулю ) это сумма по модулю произведений переменных или их отрицаний Поста, причем число отрицаний каждой переменной определяется вектором поляризации этой ППФ. Длиной ППФ называется число ее попарно различных слагаемых. Длиной функции -значной логики в классе ППФ называется минимальная длина среди всех ППФ, реализующих эту функцию. В работе построена такая последовательность симметрических функций трехзначной логики , что длина каждой из функций в классе ППФ не меньше, чем , где обозначает наибольшее целое число, не превосходящее число . Сложностью системы ППФ, имеющих один и тот же вектор поляризации, называется число попарно различных слагаемых, встречающихся во всех этих ППФ. Сложностью системы функций -значной логики, зависящих от переменных , в классе ППФ называется минимальная сложность среди всех таких систем ППФ , что все ППФ имеют один и тот же вектор поляризации, и ППФ реализует функцию , . Пусть $L_k^{\textrm{ППФ}}(m, n) = \max\limits_{F}L_k^{\textrm{ППФ}}(F)$, где индекс пробегает по всем системам, содержащим функций -значной логики, зависящих от переменных . Понятно, что при простых верна оценка . В работе доказано, что $L_2^ (m, n) = 2^n$ и для всех , . Более того, доказано, что оценки остаются такими же, если рассматривать только системы симметрических функций. Работа поддержана РФФИ, проекты 13 01 00684-а, 13 01 00958-а.