?
О сложности задачи решения линейных уравнений над конечными подстановками
С. 221-223.
Захаров В. А., Новикова Т. А.
Исследована задача решения линейных уравнений над множеством подстановок первого порядка. Получена полная классификация вычислительной сложности этой задачи в зависимости от вида уравнений.
Язык:
русский
В книге
Каз. : Отечество, 2014
Faliszewski P., Карпов А. В., Obraztsova S., , in : Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20). : International Joint Conferences on Artificial Intelligence, 2020. P. 203-209.
Добавлено: 15 июля 2020 г.
Фомин Д. Б., Прикладная дискретная математика. Приложение 2021 № 14 С. 51-55
Рассмотрены способы построения дифференциально 2δ-равномерных подстано- вок на F_{2^{2m}} для случая m≥3. Предложенный подход излагается с использованием так называемого TU-представления функций и обобщает известный способ построения дифференциально 4-равномерных подстановок поля F_{2^{2m}} с применением подстановки обращения ненулевых элементов поля. ...
Добавлено: 22 сентября 2021 г.
Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
Добавлено: 23 июня 2013 г.
Шитов Я. Н., American Mathematical Monthly 2016 Vol. 123 No. 1 P. 71-77
We present an infinite sequence of pairs (An, Bn) of chess positions on an n × n board such that (1) there is a legal sequence of chess moves leading from An to Bn and (2) any legal sequence leading from An to Bn contains at least exp(n + o(n)) moves. ...
Добавлено: 23 февраля 2016 г.
Васильев В. А., Moscow Mathematical Journal 2017 Vol. 17 No. 4 P. 825-836
Добавлено: 27 декабря 2017 г.
Рыбаков М. Н., Агаджанян И. А., / arXiv. Серия 2211.14571 "Logic". 2022.
Доказывается PSPACE-трудность константных фрагментов всех логик, лежащих между K и wGrz ...
Добавлено: 5 декабря 2022 г.
Малышев Д. С., Вестник Нижегородского университета им. Н.И. Лобачевского 2008 № 6 С. 141-146
Рассматривается понятие граничного класса, которое является полезным инструментом для анализа вычислительной сложности задач на графах. Исследуются два конкретных класса графов, и приводятся задачи, для которых эти классы являются граничными. ...
Добавлено: 31 августа 2012 г.
Малышев Д. С., Discrete Mathematics and Applications 2010 Vol. 19 No. 6 P. 625-630
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Малышев Д. С., Дискретная математика 2009 Т. 21 № 4 С. 129-134
Понятие граничного класса — полезный инструмент изучения сложности экстремальных задач на графах. В настоящее время известны один граничный класс для задачи о независимом множестве и три граничных класса для задачи о доминирующем множестве. В настоящей работе доказывается бесконечность множества граничных классов для задачи о 3-раскраске. ...
Добавлено: 25 ноября 2012 г.
Корпелайнен Н., Лозин В. В., Малышев Д. С. и др., Theoretical Computer Science 2011 No. 412 P. 3545-3554
Понятие граничного свойства графов было недавно введено в качестве релаксации минимального по включению свойства и было применено к нескольким задачам алгоритмической и комбинаторной природы. В настоящей работе мы в начале делаем обзор недавних результатов, связанных с этими понятием, а затем применяем их к двум алгоритмическим задачам: задаче о гамильтоновом цикле и задаче о вершинной k-раскраске. ...
Добавлено: 11 сентября 2012 г.
Малышев Д. С., Дискретная математика 2016 Т. 28 № 2 С. 44-50
Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, ...
Добавлено: 5 июля 2016 г.
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 22 С. 435-455
Логико-термальная эквивалентность программ – это одно из наиболее слабых отношений эквивалентности программ, аппроксимирующих отношение функциональной эквивалентности и обладающих разрешающим алгоритмом. В данной статье предложена новая модификация алгоритма проверки логико-термальной эквивалентности программ, основанная на операции вычисления точной нижней грани в решетке конечных подстановок. Показано, что трудоемкость предложенного алгоритма оценивается величиной O(n6) , где n - размер ...
Добавлено: 30 сентября 2015 г.
М. А. Коврижных, Д. Б. Фомин, Прикладная дискретная математика 2022 № 57 С. 5-21
Исследована возможность построения с помощью обобщённой конструкции подстановок с заданными криптографическими характеристиками, обеспечивающими стойкость алгоритмов шифрования к линейному и разностному методам криптоанализа. Предложен эвристический алгоритм поиска параметров обобщённой конструкции, полученных посредством умножения на транспозиции. Используются идеи генетического алгоритма, спектрально-линейного и спектрально- разностного методов. Изучены вопросы оптимизации вычисления криптографических характеристик на каждой итерации алгоритма. Экспериментальные исследования ...
Добавлено: 8 октября 2022 г.
Швыдун С. В., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Исследуются двухступенчатые процедурывыбора, которые представляют собой суперпозицию двух процедур выбора. Показано, какие из рассматриваемых процедур выбора удовлетворяют существующим нормативным условиям, описывающим, каким образом изменяется конечный выбор при изменении предъявляемого множества альтернатив и оценок альтернатив по критериям. Особое внимание уделяется двухступенчатым процедурам, в основе которых лежат позиционные правила, а также правила, использующие мажоритарное отношение, вспомогательную числовую ...
Добавлено: 20 октября 2015 г.
Сироткин Д. В., Малышев Д. С., Дискретная математика 2017 Т. 29 № 3 С. 114-125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Добавлено: 7 сентября 2017 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Добавлено: 31 августа 2012 г.
Малышев Д. С., Дискретный анализ и исследование операций 2020 Т. 27 № 4 С. 104-130
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен
сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная ...
Добавлено: 25 декабря 2020 г.
Малышев Д. С., Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48
Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...
Добавлено: 30 ноября 2012 г.
Алексеев В. Е., Лозин В. В., Малышев Д. С. и др., Lecture Notes in Computer Science 2008 Vol. 5162 No. 4 P. 96-107
В работе изучается вычислительная сложность нахождения наибольшего независимого множества вершин в планарных графах. В общем случае данная задача является NP-полной. Однако, при определенных ограничениях она становится полиномиально разрешимой. В работе выявляется графовый параметр, к изменению которого чувствительна сложность задачи и предлагаем несколько отрицательных (об NP-полноте) и положительных (о полиномиальной разрешимости) результатов, обобщающих несколько ранее известных ...
Добавлено: 7 ноября 2012 г.
Сироткин Д. В., Журнал Средневолжского математического общества 2018 Т. 20 № 2 С. 199-205
Задача о вершинной 3-раекраеке для заданного графа состоит в том, чтобы проверить, можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известно, что эта задача является NР-полной в классе планарных графов и что она становится полиномиально разрешимой для плоских триангуляций — планарных графов, у которых все грани (включая и внешнюю) являются треугольниками. ...
Добавлено: 2 июля 2018 г.
Развенская О. О., Малышев Д. С., Дискретный анализ и исследование операций 2021 Т. 28 № 1 С. 15-47
Задача о взвешенной вершинной раскраске для заданного взвешенного графа состоит в том, чтобы минимизировать количество используемых цветов так, что для каждой вершины количество назначаемых ей цветов равно ее весу и назначаемые множества цветов для любых смежных вершин не пересекаются. Для всех наследственных классов, определяемых двумя связными 5-вершинными порожденными запретами, кроме четырех случаев, известна вычислительная сложность ...
Добавлено: 15 декабря 2020 г.
Захаров В. А., Кузюрин Н. Н., Варновский Н. П. и др., Программирование 2015 № 6
Обфускацией программ называется такое эквивалентное преобразование программ, которое придает программе форму, затрудняющую понимание алгоритмов и структур данных, используемых программой, и препятствующую извлечению из текста программы определенной полезной информации, содержащейся в ней. Поскольку обфускация программ может найти широкое применение при решении многих задач криптографии и компьютерной безопасности, задаче оценки стойкости обфускации придается очень большое значение, начиная ...
Добавлено: 13 октября 2015 г.
Сироткин Д. В., Малышев Д. С., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760-766
Добавлено: 5 июня 2021 г.
Малышев Д. С., Дискретный анализ и исследование операций 2011 Т. 18 № 1 С. 70-76
Рассматривается понятие минимального сложного класса графов применительно к задаче о реберном списковом ранжировании. Для этой задачи исследуется способ получения таких классов и на его основе выявляется новый класс. Показывается полнота некоторой совокупности классов графов как системы минимальных сложных классов которые можно получить в рамках предлагаемого подхода. ...
Добавлено: 11 сентября 2012 г.