![]() |
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Цель проекта - получение структуры и свойств замкнутых классов 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 позитивно замкнутые класса; для эквационального замыкания найдены все замкнутые классы булевых функций, а также частичных булевых функций; для оператора замыкания по перечислению (П-оператор) определены все замкнутые классы булевых функций; доказано, что всякий позитивно замкнутый класс является П-замкнутым. Балюком А.С. совместно с Янушковским Г. В. предложено обобщение операторных форм булевых функций на случай функций над конечными полями, использованный подход позволил обобщить почти все ранее известные классы. Кроме того, Балюком А. С. предложены методы получения верхних и нижних оценок сложности функций над конечными полями в классах поляризованных полиномов и кронекеровых форм, основанные на использовании расширений конечных полей. Селезневой С.Н. разработаны методы, при помощи которых получены оценки сложности функций над конечным полем в различных классах полиномиальных форм; некоторые из этих оценок являются точными. Селезневой С.Н. получена полная классификация сложности задачи выполнимости мультилинейных форм над конечным полем.
МГУ имени М.В.Ломоносова | Координатор |
грант РФФИ |
# | Сроки | Название |
1 | 1 января 2019 г.-31 декабря 2019 г. | Структурные и сложностные вопросы в теории k- значных функций |
Результаты этапа: Рассмотрена задача расшифровки монотонных функций алгебры логики при возможном одном неверном ответе на запросы. Доказано, что в случае, когда ответы на запросы не нарушают возможность правильно восстановить функцию, можно исправить ошибку и восстановить неизвестную монотонную функцию, не увеличивая сложности расшифровки. Построена классификация сложности кванторной задачи удовлетворения ограничениям на трехэлементном множестве. Доказано, что при любом k > 1 операторы эквационального замыкания и замыкания по перечислению порождают одну и ту же классификацию на множестве частичных функций k-значной логики. Найдены критерии однозначности алфавитного кодирования сверхслов для конечного и бесконечного кодов. Доказано, что в случае бесконечного кода проблема распознавания неоднозначности кода является m-полной в классе Е1А0 аналитической иерархии Клини. Улучшена верхняя оценка сложности трехзначных функций в классе поляризованных полиномов. Получена нижняя оценка сложности булевых функций в классе расширенных операторных форм, улучшающая ранее известные оценки и являющаяся асимптотически оптимальной в случае бесконечности последовательности простых чисел Мерсенна. | ||
2 | 1 января 2020 г.-31 декабря 2020 г. | Структурные и сложностные вопросы в теории k- значных функций |
Результаты этапа: Исследовалась структура решетки замкнутых классов в частичной k-значной логике. Пусть A - клон (замкнутый класс, содержащий все селекторы) в k-значной логике. Через Str(A) обозначается замкнутый класс всех частичных функций, которые могут быть доопределены до какой-нибудь функции из A. Доказано, что интервал Int(A) всех замкнутых классов, лежащих между A и Str(A) (с отношением включения) изоморфен семейству Z(A) всех подмножеств предикатов на {0, 1, ... , k-1}, содержащих все предикаты, тождественно равные 1, и замкнутых относительно добавления и изъятия фиктивных переменных, конъюнкции предикатов и подстановки в предикаты функций из A (с отношением включения). С использованием этого соответствия доказаны 2 утверждения. 1) Если A - клон, состоящий только из селекторов, то Int(A) имеет мощность континуума. 2) Если k - произведение двух различных простых чисел и Pol - множество всех функций k-значной логики, представимых полиномом по модулю k, то Int(Pol) состоит ровно из 7 замкнутых классов, которые полностью описаны. На множестве частичных функций k-значной логики рассмотрен оператор импликативногозамыкания - расширение оператора параметрического замыкания с помощью связки импликации. Доказано, что при любом k > 1 число импликативно замкнутых классов конечно. Определены две серии импликативно классов и установлено, что эти две серии исчерпывают все импликативно предполные классы. Рассмотрен класс ЕР экспоненциально-полиномиальных функций, которые можно получить произвольными суперпозициями из функций 0, 1, x + y, xy, x^y. В классе ЕР эффективно определены 6 предполных (относительно операции суперпозиции) классов, на основе которых сформулированы критерий полноты и алгоритм распознавания полноты конечных систем функций. Удалось доказать, что задача No-Rainbow Problem является NP-полной. Эта задача - самый известный пример сюръективной задачи удовлетворения ограничениям, для которой сложность не была описана. Была опровергнута гипотеза Хуби Чена о сложности сюръективной задачи удовлетворения ограничениям, а также показано, что сложность этой задачи не может быть описана в терминах полиморфизмов. Получены свойства мультиаффинных многочленов над конечным полем. Доказано, что для произвольного многочлена над заданным конечным полем с полиномиальной сложностью можно проверить его мультиаффинность и при положительном ответе найти его приведенное представление. | ||
3 | 1 января 2021 г.-31 декабря 2021 г. | Структурные и сложностные вопросы в теории k- значных функций |
Результаты этапа: |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".