![]() |
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Исследование дискретных функций в следующих направлениях: исследование сложности представление функций алгебры логики и функций многозначных логик полиномиальными формами различных видов; исследование мультипликативной сложности функций алгебры логики; исследование сложности проверки по полиному функции алгебры логики или функции многозначной логики ее принадлежности некоторым важным классам; построение описания ключевых предикатов, допускающих слабую функцию почти единогласия и дальнейшее применение этого описания для построение решёток замкнутых классов; исследование гипотез для 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. Получены характеризация замкнутых классов полиномов над бесконечными числовыми кольцами, сохраняющих разбиения, и состав таких классов.
МГУ имени М.В.Ломоносова | Координатор |
грант РФФИ |
# | Сроки | Название |
1 | 1 января 2013 г.-31 декабря 2013 г. | Алгоритмические, оптимизационнные и структурные вопросы в теории дискретных функций |
Результаты этапа: При выполнении проекта в 2013 г. получены следующие результаты. Построен субэкспоненцианьный алгоритм решения задачи распознавания принадлежности функций алгебры логики, заданных полиномами Жегалкина, к классам Поста Oi. Доказана полиномиальность задачи распознавания периодичности булевой функции, заданной полиномом Жегалкина, относительно заданного периода. Построено конструктивное описание вида стационарных функций трехзначной логики, которое позволяет по известным стационарным функциям строить стационарные функции от большего числа переменных. Описана иерархия всех стационарных классов в трехзначной логике, разработан алгоритм подсчета числа функций в стационарных классах. Доказана достижимая нижняя оценка алгоритмической сложности (в модели СФЭ в базисе из одного элемента сложения по модулю два) построения полинома Жегалкина для функций алгебры логики, зависящих от двух и от трех переменных. Установлен порядок функции Шеннона длины функций k-значной логики полиномиальными нормальными формами по модулю k (при простых k). Получен критерий наличия бесконечной надструктуры у классов монотонных функций, порожденных частично упорядоченным множеством с единственным минимальным и тремя максимальными элементами; описана надструктура класса, равного пересечению всех классов квазисамодвойственных функций. Найдены верхняя и нижняя оценки для минимальной арности функции почти единогласия, сохраняющей некоторое множество предикатов арности N. Это позволило доказать алгоритмическую разрешимость следующей проблемы: дано конечное множество предикатов, существует ли функция почти единогласия, сохраняющая это множество предикатов. Разработан метод, позволяющий строить решётки замкнутых классов функций, содержащих функцию почти единогласия, с помощью компьютера. Это позволило найти все замкнутые классы, содержащие функцию голосования трёхзначной логики (всего их 1 918 040). Построена решетка, исследованы различные свойства решетки замкнутых классов и самих замкнутых классов. Получена верхняя оценка минимальной арности функции почти единогласия в конечно порождённом замкнутом классе. Найдены оценки количества и максимальной цепи из замкнутых классов, содержащих функцию почти единогласия и заданных предикатами арности n. Доказано, что все замкнутые классы трехзначной логики с функцией голосования порождаются функциями арности 5, а в четырёхзначной логике функциями арности 8, и эти значения не могут быть уменьшены. Разработаны алгоритмы распознавания свойств полиномов, важных с точки зрения полноты в системе L(Z) линейных полиномов над кольцом целых чисел. Разработан полиномиальный алгоритм распознавания полноты в системе L(Z). Доказаны критерии полноты в L(Z) систем, содержащих классы K_0 всех нечетных функций, K_1 всех унарных функций, K_E всех полиномов со свободным коэффициентом, кратным E (E\ge 2), K_M всех полиномов, сохраняющих модуль, K_S всех сюръекций. Разработаны алгоритмы распознавания полноты в L(Z) таких систем. Для всех разработанных алгоритмов были получены оценки их временной и емкостной сложности. Установлен состав замкнутых классов U(R) в функциональных системах P(A), сохраняющих разбиения R множества A на промежутки равной длины. Найдены полные системы и базисы в классах U(R). Выявлены случаи бесконечной порожденности и отсутствия базиса. Описаны бесконечные фрагменты решеток классов U(R). | ||
2 | 1 января 2014 г.-31 декабря 2014 г. | Алгоритмические, оптимизационнные и структурные вопросы в теории дискретных функций |
Результаты этапа: При выполнении проекта в 2014 г. были получены следующие результаты. Найдены верхняя и нижняя оценки длины функций алгебры логики в классе псевдополиномиальных форм. Получен порядок длины функций k-значных логик в классе полиномиальных нормальных форм (при простых k). Найдены точные значения мультипликативной сложности некоторых функций алгебры логики. Получены полиномиальные алгоритмы проверки некоторых соотношений между множеством значений функции алгебры логики и коэффициентами её полинома Жегалкина. Найдены мощности классов частично стационарных функций трехзначной логики. Предложено описание всех ключевых отношений, сохраняющихся функцией почти единогласия, где ключевые отношения – все отношения необходимые для задания замкнутых классов функций. Показано, что это описание полезно для решения различных задач, в том числе алгоритмических задач, связанных с функциями k-значной логики. Описаны решетки замкнутых классов полиномов над кольцом Z_k при k=p^m, где p - простое число, содержащих все полиномы первой степени. В функциональных системах полиномов над некоторыми бесконечными кольцами выяснен состав замкнутых классов сохранения некоторых эквивалентностей и классов сохранения конечных множеств и множеств с конечным дополнением. Исследована связь арифметических полиномов и функциональной системы полиномов над кольцом целых чисел. | ||
3 | 1 января 2015 г.-31 декабря 2015 г. | Алгоритмические, оптимизационнные и структурные вопросы в теории дискретных функций |
Результаты этапа: При выполнении проекта в 2015 г. получены следующие результаты. Получены точные значения функции Шеннона сложности систем функций двузначной и трехзначной логик в классах поляризованных полиномиальных форм. Построен полиномиальный алгоритм проверки равенства двух полиномов функций алгебры логики, поляризованных по разным векторам. Усилена полученная ранее верхняя оценка минимальной арности функции почти единогласия в замкнутом классе, порождённом функциями ограниченной арности, получена нижняя оценка, для идемпотентного случая показано, что нижняя оценка является точной. Найдено точное описание ключевых предикатов с полным шаблоном. Решена открытая проблема о минимальном размере порождающего множества для декартовых степеней конечной алгебры. Показано, что для любой алгебры размер минимального порождающего множества либо ограничен сверху полиномом от степени, либо ограничен снизу экспонентой. Более того, для идемпотентного случая был получен простой критерий существования полиномиального порождающего множества. Показано, что невозможно проверить наличие в алгебре термальной операции минорирования никакими локальными свойствами даже в идемпотентном случае. А именно, для произвольного N была построена идемпотентная алгебра с 4N элементами, которая не содержит термальную операцию минорирования, но на любом (N-1)-элементном подмножестве такая операция может быть найдена. В системе линейных полиномов над кольцом целых чисел L(Z) построены решётки замкнутых классов по включению, изоморфные решётке натуральных чисел по отношению делимости. В системе L(Z) найдены алгоритмы распознавания полноты относительно замкнутых классов, входящих в решётки по включению. В k–значной логике описано семейство замкнутых классов S(d) , где d - делитель числа k, найдено их место в решетке всех замкнутых классов. Построена решетка замкнутых классов полиномов в p^2–значной логике, включающая класс S(p), выяснены особенности решетки в p^m–значной логике при m>2. В функциональных системах полиномов над бесконечными числовыми кольцами описаны замкнутые классы сохранения разбиений с одним бесконечным блоком, выяснен состав таких классов. |
Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".