Структурные и алгоритмические проблемы для дискретных математических моделейНИР

Structural and algorithmical problems for discrete mathematical models

Соисполнители НИР

МГУ имени М.В.Ломоносова Координатор

Источник финансирования НИР

госбюджет, раздел 0110 (для тем по госзаданию)

Этапы НИР

# Сроки Название
1 1 января 2021 г.-31 декабря 2021 г. Структурные и алгоритмические проблемы для дискретных математических моделей
Результаты этапа: Доказано, что множество всех замкнутых классов в частичной k-значной логике, содержащих все полиномы по модулю k и состоящих только из функций, доопределимых до полиномов, конечно тогда и только тогда, когда k – простое число или произведение двух различных простых чисел. Доказано, что при любом k > 1 любой позитивно предполный класс в Pk является также предполным относительно оператора замыкания по перечислению (П-замыкание). В качестве следствия установлено, что в трехзначном случае других П-предполных классов нет. Полученныеые результаты позволяют значительно продвинуться в исследовании сильного оператора П-замыкания и, в частности, создают базу для определения всей решетки П-замкнутых классов в Pk. Исследованы бесконечно-порожденные замкнутые классы П1 – П4 01-функций трехзначной логики. Доказана максимальность классов П3, П4 в решетке всех замкнутых классов 01-функций трехзначной логики. Найдены все «простейшие» функции от двух или трех переменных, которые можно получить суперпозициями из произвольной функции, не принадлежащей классу П1, и которые не принадлежат классу П1. Этот результат позволит определить все максимальные бесконечно-порожденные классы 01-функций. Получена невырожденная постановка задачи легализации ответа – имитация решения диофантова уравнения. Доказана линейность функции Шеннона для теста относительно бесповторной альтернативы в элементарном базисе, расширенном всеми монотонными функциями Стеценко. Найдена булева функция n переменных, порождающая семейство большее, чем все функции n-1 переменной Разработан алгоритм проверки периодичности функций алгебры логики, заданных многочленами Жегалкина. Получены условия, при которых вершины псевдокубических и 2-псевдокубических графов можно раскрасить в три цвета. Доказано, что мощность максимального базисе четырёхзначной логики не менее 19 и не более 46. Построен полиномиальный алгоритм, который получает на вход обобщённый полином и выдаёт все тождества определенного вида, применение которых к входному обобщенному полиному уменьшает его длину. Практическая значимость: результаты теоретические, направленные на более глубокое понимание свойств дискретных функций и графов.
2 1 января 2022 г.-31 декабря 2022 г. Структурные и алгоритмические проблемы для дискретных математических моделей
Результаты этапа: Установлен ряд свойств, которыми должен обладать билинейный алгоритм сложности 17 для умножения матрицы порядка 2 на матрицу размера 2 x 5, если он существует. Это дает существенное продвижение в задаче установления точной билинейной сложности умножения матрицы порядка 2 на матрицу размера 2 x 5 (17 или 18). В задаче о сложности умножения матрицы размера m x s на матрицу размера s x n над конечными полями удалось повысить нижнюю оценку билинейной сложности этой задачи. Найден алгоритм, который определяет равенство/неравенство любых двух одноместных функций из класса РЕР экспоненциально-полиномиальных функций натуральных аргументов. Алгоритм позволит в дальнейшем решить проблему равенства конечно-порожденных классов в РЕР. Доказано, что для целочисленных полиномиальных возвратных последовательностей существуют PSPACE-полные алгоритмические проблемы. Этот результат задает нижнюю границу сложности рассматриваемых возвратных последовательностей. Установлено, что для целочисленных возвратных последовательностей, порождающие функции которых определяются суперпозициями полиномиальных функций и функции |x|, существуют алгоритмически неразрешимые проблемы. Данный результат показывает, что добавление к полиномиальным функциям «почти линейной» функции |x| приводит к возвратным последовательностям с алгоритмически неразрешимыми проблемами. Доказано, что логические обобщения неявной выразимости А.В. Кузнецова дают лишь три новые неявные выразимости: дизъюнктивную, импликативную и негативную. Это закрывает вопрос о возможных логических обобщениях неявной выразимости А.В. Кузнецова. Найден алгоритм построения некоторого псевдополинома для функции функции алгебры логики. Получены результаты его работы для функций четырех переменных и проведено их сравнение с известными результатами. Доказана верхняя оценка длины псевдополиномов, получаемых этим алгоритмом для функций n переменных. Получен полиномиальный алгоритм проверки мультиаффинности многочлена над конечным простым полем (по отношению к заданному элементу этого поля). Алгоритм упрощает известные алгоритмы решения этой задачи. Рассмотрена задача условного тестирования для произвольных контактных схем, реализующих сумму по модулю два, в случае неограниченного числа неисправностей типа замыкания и размыкания. Оценена глубина полного диагностического теста. Рассмотрена задача нахождения универсальных функций простого вида для класса линейных функций двух переменных. Получен критерий универсальности функции xy. Доказано совпадение класса BPC, определенного с помощью операции ограниченной префиксной конкатенации, с известным сложностным классом TC0. Благодаря этому прояснен ряд свойств класса BPC и получено простое чисто словарное определение класса TC0. Результаты теоретические, направленные на более глубокое понимание свойств дискретных функций, структуры быстрых алгоритмов и классов сложности.
3 1 января 2023 г.-31 декабря 2023 г. Структурные и алгоритмические проблемы для дискретных математических моделей
Результаты этапа: Решетки Int(A) всех замкнутых классов в частичной 2-значной логике, содержащих все функции из замкнутого класса A 2-значной логики и состоящих только из функций, доопределимых до некоторой функции из класса A, полностью описаны для всех случаев, когда A - это любое пересечение классов монотонных функций M и классов функций, сохраняющих константы T0 и T1. Найдена серия «ключевых» функций индикаторного типа, которые вместе с полиномиальными функциями позволяют определять почти полиномиальные возвратные последовательности с алгоритмически неразрешимыми проблемами. Это приближает решение проблемы о сложности полиномиальных возвратных последовательностей. Доказано, что семейства позитивно, импликативно и негативно неявных расширений в многозначной логике собственным образом включают соответствующие семейства замкнутых классов. Тем самым установлено отличие операторов неявных расширений всех указанных типов от соответствующих операторов замыкания. Оценена сложность проверки периодичности функций, заданных полиномами над конечным простым полем. А именно, построен алгоритм, который для каждого заданного конечного простого поля по полиному над этим полем находит базис линейного пространства всех периодов функции, определяемой этим полиномом, и найден порядок сложности этого алгоритма. В случае полиномов ограниченной степени алгоритм имеет полиномиальную сложность относительно числа переменных полинома. Получен для каждого конечного поля полиномиальный алгоритм, который по многочлену над этим полем и по элементу этого поля проверяет, является ли этот многочлен мультиаффинным относительно этого элемента. При положительном ответе алгоритм находит некоторое приведенное представление соответствующего равенства. Начато исследование описания замкнутого класса полиномиальных функций по модулю степени простого числа. На основе проанализированной литературы, относящейся к классам AC0 и TC0, введены или уточнены некоторые приёмы доказательств, связанные с этими классами (в том числе, в связи с доказательством принадлежности функции умножения классу TC0). Выявлены связи TC0 с некоторыми другими изучавшимися в литературе классами. Получено новое тождество, уменьшающее длину, которое не выводится из полученных ранее. Получена полная система тождеств, уменьшающих длину, для обобщенных полиномов от не более, чем трех переменных. Сформулировано необходимое условие минимальности обобщенных полиномов на базе системы тождеств.
4 1 января 2024 г.-31 декабря 2024 г. Структурные и алгоритмические проблемы для дискретных математических моделей
Результаты этапа: Для класса булевых функций S01, состоящего из всех самодвойственных функций, сохраняющих 0 и 1, доказано, что замкнутых классов в частичной 2-значной логике, содержащих класс S01 и состоящих только из функций, доопределимых до какой-нибудь функции из S01, имеется ровно 91, и дано описание этих классов. В трехзначной логике описаны импликативно неявные расширения всех 27 одноместных функций и всех 27 двуместных симметрических функций, сохраняющих три константы. Доказано, что в любом импликативно неявном расширении множество всех n-местных отношений (n-система) образует булеву алгебру с теоретико-множественными операциями объединения, пересечения и (относительного) дополнения. В трехзначном случае описаны все 2-системы отношений, принадлежащих импликативно неявным расширениям. Продолжено исследование замкнутого класса Polpm функций, полиномиальных по модулю степени m простого числа p. Для класса Polp2 установлены критерии принадлежности. На основе этих критериев получены в явном виде отношения, описывающие класс Polp2. В случае любого простого числа p местность отношений равна четырем; при нечетных простых числах p местность отношений можно уменьшить до трех. Для класса Polpm предложен распознающий алгоритм для функций одной переменной. Установлен порядок сложности этого алгоритма при росте числа m (относительно операций сложения и умножения в простом поле из p элементов с возможным применением констант). Получена нижняя оценка числа антицепей в частично упорядоченных множествах, являющихся декартовой степенью множества S(c,b), отличная от тривиальной. Диаграмма Хассе частично упорядоченного множества S(c,b) представляет собой «полный» трехдольный граф, мощности слоев которого равны c, b, с соответственно. Систематизированы некоторые результаты, связанные со счётчиковыми машинами с сумматором: уточнены определения и доказательства. Введена новая модель абстрактной машины, близкая к счётчиковым машинам с сумматором, позволяющая производить обратимые вычисления. Получен полиномиальный алгоритм для проверки принадлежности функции алгебры логики, заданной полиномом, к классу O2 в случае, если степень полинома ограничена константой. Практическая значимость: часть исследований являются теоретическими, они направлены на более глубокое понимание свойств дискретных функций, частично-упорядоченных множеств и графов; часть исследований могут применяться на практике, они направлены на ускорение работы прикладных алгоритмов.

Прикрепленные к НИР результаты

Для прикрепления результата сначала выберете тип результата (статьи, книги, ...). После чего введите несколько символов в поле поиска прикрепляемого результата, затем выберете один из предложенных и нажмите кнопку "Добавить".

Прикрепленные файлы

№ Имя Описание Имя файла Размер Добавлен