ИСТИНА

Цель проекта - получение структуры и свойств замкнутых классов k-значных функций, а также нахождение сложности и свойств представлений таких функций различными формами. Последние результаты по сложности задачи удовлетворения ограничениям, полученные с помощью алгебраического подхода, показали, что алгоритмическая задача может быть простой или сложной в зависимости от наличия операций, сохраняющих ограничения. Поэтому на первый план выходит исследование решетки замкнутых классов функций, а также строения позитивных-примитивных формул, которые позволяют выводить новые отношения/предикаты. В проекте предполагается выполнить это исследование, а также применить его результаты к конкретным алгоритмическим задачам. В настоящее время интенсивно исследуются сильные операторы замыкания, порождающие конечные классификации множества функций многозначной логики. Известно около 10 сильных операторов замыкания, однако для большинства из них соответствующие классификации не описаны даже в трехзначном случае. В проекте предполагается описать решетки замкнутых классов для трех сильных операторов замыкания, а также найти соотношение операторов между собой. Недавно получено существенное продвижение в вопросах сложности представлений функций над конечным полем и их систем различными обобщенными полиномиальными формами, однако окончательные результаты пока не найдены. В проекте предполагается развить операторный подход к построению представлений функций над конечными полями, обобщающих полиномиальные представления; найти нижние и верхние оценки сложности таких представлений и улучшить известные оценки; получить свойства и оценки сложности некоторых представлений функций и предикатов над конечным множеством.

In the project we plan to study the structure and properties of different closed classes of k-valued functions, and to describe the complexity and properties of different representations of k-valued functions. Recently the complexity of the constraint satisfaction problem was described in terms of operations preserving the constraint language. This operation can be viewed as a symmetry of the input language, and the problem is tractable (can be solved in polynomial time) if such a symmetry exists. Thus, to study the complexity of this and similar problems we need to learn the connection between operations and relations, properties of the lattice of clones, and the structure of positive-primitive formulas. In the project we plan to fulfill such an investigation and apply the results to describe the complexity of different algorithmic problems. Strong closure operators generating only finitely many closed classes are intensively studied for multiple-valued logic functions. About 10 strong closure operators are known, but none of them has a complete description of all closed classes even for three-valued case. In the project we plan to investigate the lattices of closed classes for three strong closure operators and to find a relationship between them. Recently substantial results were obtained for the complexity of functions over a finite field in different classes of generalized polynomial forms, but final results were not yet found. In the project we plan to introduce an operator based approach to generalization of polynomials, to find lower and upper bounds on the complexity of functoins over a finite field in classes of operator forms, to obtain properties and complexity of certain representations of functions and predicates over a finite set.

Исследовать связь замкнутых классов k-значных функций и отношений с алгоритмической сложностью различных вариантов задачи обобщенной выполнимости. Исследовать сильные операторы замыкания, получить критерии полноты и описать решетки их замкнутых классов. Найти сложность k-значных функций в различных классах полиномиальных форм. Получить свойства предикатов и функций над конечным множеством.

Жук Д.Н. получил описание всех критичных (ключевых) предикатов, что в дальнейшем было использовано для описания сложности задачи обобщенной выполнимости на конечных множествах и неявно в некоторых других задачах. Марченковым С.С. для позитивного замыкания при любом k>1 определены все предполные классы в k-значной логике; в трехзначной логике найдены все 192 позитивно замкнутые класса; для эквационального замыкания найдены все замкнутые классы булевых функций, а также частичных булевых функций; для оператора замыкания по перечислению (П-оператор) определены все замкнутые классы булевых функций; доказано, что всякий позитивно замкнутый класс является П-замкнутым. Балюком А.С. совместно с Янушковским Г. В. предложено обобщение операторных форм булевых функций на случай функций над конечными полями, использованный подход позволил обобщить почти все ранее известные классы. Кроме того, Балюком А. С. предложены методы получения верхних и нижних оценок сложности функций над конечными полями в классах поляризованных полиномов и кронекеровых форм, основанные на использовании расширений конечных полей. Селезневой С.Н. разработаны методы, при помощи которых получены оценки сложности функций над конечным полем в различных классах полиномиальных форм; некоторые из этих оценок являются точными. Селезневой С.Н. получена полная классификация сложности задачи выполнимости мультилинейных форм над конечным полем.