ИСТИНА

Исследование дискретных функций в следующих направлениях: исследование сложности представление функций алгебры логики и функций многозначных логик полиномиальными формами различных видов; исследование мультипликативной сложности функций алгебры логики; исследование сложности проверки по полиному функции алгебры логики или функции многозначной логики ее принадлежности некоторым важным классам; построение описания ключевых предикатов, допускающих слабую функцию почти единогласия и дальнейшее применение этого описания для построение решёток замкнутых классов; исследование гипотез для Constraint Satisfaction Problem; изучение свойств и новых фрагментов надрешетки замкнутых классов монотонных функций многозначной логики; описание замкнутых классов и их решеток в некоторых функциональных системах полиномов над кольцом целых чисел; изучение применения полиномиальных представлений дискретных функций в задачах информационного поиска и классификации.

При выполнении проекта получены следующие результаты. Получены точные значения функции Шеннона сложности систем функций двузначной и трехзначной логик в классах поляризованных полиномиальных форм. Найдены оценки функции Шеннона длины функций алгебры логики в классе псевдополиномиальных форм. Получен порядок функции Шеннона длины функций k-значной логики в классе полиномиальных нормальных форм по модулю k. Найдены точные значения мультипликативной сложности функций алгебры логики, представимых суммой по модулю два произведения всех переменных и квадратичной функции или двух мультиаффинных функций, а также точное значение функции Шеннона мультипликативной сложности в одном классе квазиквадратичных функций алгебры логики. Доказана полиномиальность задачи проверки совпадения множества единиц функции алгебры логики, заданной полиномом Жегалкина, с заданным образцом. Построен субэкспоненциальный алгоритм проверки сохранения функцией алгебры логики, заданной полиномом Жегалкина, заданного центрального предиката. Построен полиномиальный алгоритм проверки равенства функций алгебры логики, заданных двумя поляризованными полиномами. Построены верхняя и нижняя оценки для минимальной арности функции почти единогласия, сохраняющей некоторое множество предикатов арности N. Это позволило доказать алгоритмическую разрешимость следующей проблемы: дано конечное множество предикатов, существует ли функция почти единогласия, сохраняющая это множество предикатов. Разработан метод, позволяющий строить решетки замкнутых классов функций, содержащих функцию почти единогласия, с помощью компьютера. С помощью этого метода удалось найти все замкнутые классы, содержащие функцию голосования трехзначной логики (всего их 1 918 040). Построена решетка, исследованы различные свойства решетки замкнутых классов и самих замкнутых классов. Получена верхняя оценка минимальной арности функции почти единогласия в конечно порожденном замкнутом классе, точная в идемпотентном случае и полиномиальная в общем случае. Найдены оценки количества и длины максимальной цепи замкнутых классов, содержащих функцию почти единогласия и заданных предикатами арности n. Доказано, что все замкнутые классы трехзначной логики с функцией голосования порождаются функциями арности 5, а в четырёхзначной логике функциями арности 8, и эти значения не могут быть уменьшены. Получено описание всех ключевых отношений, сохраняющихся функцией почти единогласия. Оказывается, что для любых замкнутых классов функций нам достаточно ключевых отношений, а в случае наличия функции почти единогласия все такие отношения имеют красивое описание. Показано, что в двухзначном случае любое такое отношение описывается как дизъюнкция линейных уравнений, где только одно уравнение содержит более одной переменной. Оказалось, что это утверждение почти без изменений может быть обобщено на k-значный случай. Решена открытая проблема о минимальном размере порождающего множества для декартовых степеней конечной алгебры. Показано, что для любой алгебры размер минимального порождающего множества либо ограничен сверху полиномом от степени, либо ограничен снизу экспонентой. Более того, для идемпотентного случая был получен простой критерий существования полиномиального порождающего множества. Показано, что невозможно проверить наличие в алгебре термальной операции минорирования никакими локальными свойствами даже в идемпотентном случае. А именно, для произвольного N была построена идемпотентная алгебра с 4N элементами, которая не содержит термальную операцию минорирования, но на любом (N-1)-элементном подмножестве такая операция может быть найдена. Это первое условие Мальцева, где есть такой пример. Получены точные значения мощности стационарных классов функций в трехзначной логике, улучшена оценка сложности алгоритма распознавания стационарности функций. Получены результаты в системе L(Z) линейных полиномов над кольцом целых чисел. Построен алгоритм распознавания полноты в системе L(Z). В системе L(Z) построены решётки замкнутых классов по включению, изоморфные решётке натуральных чисел по отношению делимости, найдены алгоритмы распознавания полноты относительно замкнутых классов, входящих в решётки по включению. Получены оценки временной и емкостной сложности всех предложенных алгоритмов. Получены критерии относительной полноты, алгоритмы и оценки сложности распознавания относительной полноты в системе L(Z). Построена решетка замкнутых классов полиномов по модулю k при k=p^2. Получены характеризация замкнутых классов полиномов над бесконечными числовыми кольцами, сохраняющих разбиения, и состав таких классов.