?
О сложности задачи решения линейных уравнений над конечными подстановками
С. 221–223.
Захаров В. А., Новикова Т. А.
Исследована задача решения линейных уравнений над множеством подстановок первого порядка. Получена полная классификация вычислительной сложности этой задачи в зависимости от вида уравнений.
Язык:
русский
В книге
Каз.: Отечество, 2014.
Дудаков С. М., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и ...
Добавлено: 18 марта 2026 г.
Сперанский С. О., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Добавлено: 27 декабря 2025 г.
Дахно Г. С., Малышев Д. С., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Добавлено: 26 ноября 2025 г.
Оноприенко А. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае ...
Добавлено: 23 ноября 2025 г.
Рыбаков М. Н., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...
Добавлено: 21 июня 2025 г.
Кудинов А. В., Рыбаков М. Н., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 36–39.
Показано, что каждая модальная логика, содержащая классическую логику высказываний и содержащаяся в слабой логике Гжегорчика, имеет NP-трудную проблему выполнимости для константного фрагмента. В частности, константные фрагменты ненормальных модальных логик E, EM, EN и EMN являются coNP-полными. ...
Добавлено: 21 июня 2025 г.
Сапронов Ю. Ф., Юдин Н. Е., Computational Mathematics and Mathematical Physics 2025 Vol. 65 No. 3 P. 567–581
We continue to develop the concept of studying the ε-optimal policy for Average Reward Markov Decision Processes (AMDP) by reducing it to Discounted Markov Decision Processes (DMDP). Existing research often stipulates that the discount factor must not fall below a certain threshold. Typically, this threshold is close to one, and as is well-known, iterative methods ...
Добавлено: 10 июня 2025 г.
Дахно Г. С., Малышев Д. С., Математические заметки 2025 Т. 117 № 1 С. 62–78
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, а имеется ли в нем такое подмножество вершин заданного размера, что каждая вершина вне подмножества имеет хотя бы одного соседа в данном подмножестве. ...
Добавлено: 3 декабря 2024 г.
G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31
Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Если это множество конечно, то он называется конечно определенным. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определенных классов. Задача о доминирующем множестве для заданного графа состоит в ...
Добавлено: 6 декабря 2022 г.
Рыбаков М. Н., Агаджанян И. А., / arXiv. Серия 2211.14571 "Logic". 2022.
Доказывается PSPACE-трудность константных фрагментов всех логик, лежащих между K и wGrz ...
Добавлено: 5 декабря 2022 г.
Малышев Д. С., Дугинов О. И., Дискретный анализ и исследование операций 2022 Т. 29 № 2 С. 38–61
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы смежные рёбра были окрашены в разные цвета. Для всех классов графов, определяемых множествами запрещённых подграфов с 7 рёбрами каждый, известен сложностной статус данной задачи. В настоящей работе рассматривается случай запретов с 8 рёбрами. Нетрудно заметить, что задача о рёберной раскраске будет ...
Добавлено: 15 ноября 2022 г.
М. А. Коврижных, Д. Б. Фомин, Прикладная дискретная математика 2022 № 57 С. 5–21
Исследована возможность построения с помощью обобщённой конструкции подстановок с заданными криптографическими характеристиками, обеспечивающими стойкость алгоритмов шифрования к линейному и разностному методам криптоанализа. Предложен эвристический алгоритм поиска параметров обобщённой конструкции, полученных посредством умножения на транспозиции. Используются идеи генетического алгоритма, спектрально-линейного и спектрально- разностного методов. Изучены вопросы оптимизации вычисления криптографических характеристик на каждой итерации алгоритма. Экспериментальные исследования ...
Добавлено: 8 октября 2022 г.
D. B. Fomin, M. A. Kovrizhnykh, Математические вопросы криптографии 2022 Vol. 13 No. 2 P. 37–52
Работа посвящена теоретическому обоснованию направленного поиска 8-битовых подстановок с заданными криптографическими характеристиками: дифференциальной δ-равномерностью и нелинейностью. Сформулированы и доказаны утверждения о разбиении на классы эквивалентности множества векторных булевых функций, построенных с помощью обобщенной конструкции. Обоснованы утверждения, позволяющие отбраковывать функции из классов эквивалентности либо по высокому показателю дифференциальной δ-равномерности, либо вследствие того, что они не являются подстановками. Результаты ...
Добавлено: 24 августа 2022 г.
Рыбаков М. Н., Вестник Тверского государственного университета. Серия: Прикладная математика 2021 № 3 С. 5–17
Приводится доказательство PSPACE-полноты проблемы равенства слов в классе всех нуль-порождённых модальных алгебр, или, эквивалентно, проблемы равенства константных слов в классе всех модальных алгебр. Также рассматривается вопрос о сложности равенства слов в произвольном многообразии модальных алгебр. Доказывается, что уже проблема равенства константных слов в многообразии модальных алгебр может быть сколь угодно трудной (включая как классы сложности, ...
Добавлено: 13 ноября 2021 г.
Фомин Д. Б., Прикладная дискретная математика. Приложение 2021 № 14 С. 51–55
Рассмотрены способы построения дифференциально 2δ-равномерных подстано- вок на F_{2^{2m}} для случая m≥3. Предложенный подход излагается с использованием так называемого TU-представления функций и обобщает известный способ построения дифференциально 4-равномерных подстановок поля F_{2^{2m}} с применением подстановки обращения ненулевых элементов поля. ...
Добавлено: 22 сентября 2021 г.
Коврижных М. А., Фомин Д. Б., Прикладная дискретная математика. Приложение 2021 № 14 С. 181–184
Предложен эвристический алгоритм построения биективных булевых функций с заданными криптографическими свойствами — нелинейностью и дифференциальной δ-равномерностью — на основе обобщённой конструкции. Производится поиск вспомогательных подстановок меньшей размерности в обобщённой конструкции с использованием идей спектрально-линейного и спектрально-разностного методов. Исследована возможность оптимизации вычисления криптографических характеристик на каждой итерации алгоритма. Экспериментально получены 8-битовые 6-равномерные подстановки с нелинейностью 108. ...
Добавлено: 22 сентября 2021 г.
Авраамова О. Д., Фомин Д. Б., Серов В. А. и др., Математические вопросы криптографии 2021 Vol. 12 No. 2 P. 21–38
Рассматриваются способы реализации нелинейного преобразования блочного алгоритма шифрования с длиной блока 128 бит «Кузнечик» (ГОСТ Р 34.12-2015) и хеш-функции «Стрибог» (ГОСТ Р 34.11-2012). Показана возможность реализации подстановки за 226 логических операций. ...
Добавлено: 26 июля 2021 г.
Сироткин Д. В., Малышев Д. С., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760–766
Добавлено: 5 июня 2021 г.
Малышев Д. С., Дискретный анализ и исследование операций 2020 Т. 27 № 4 С. 104–130
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен
сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная ...
Добавлено: 25 декабря 2020 г.
Развенская О. О., Журнал Средневолжского математического общества 2020 Т. 22 № 4 С. 442–448
Классическая NP-трудная задача о взвешенной вершинной раскраске состоит в минимизации количества цветов в раскрасках вершин задаваемого графа так, что для каждой вершины назначаются цвета, количество которых равно задаваемому весу вершины, причем смежным вершинам назначаются различные цвета. Соответствующее наименьшее количество цветов называется взвешенным хроматическим числом графа. Известно несколько полиномиальных алгоритмических приемов для построения эффективных алгоритмов для ...
Добавлено: 16 декабря 2020 г.
Развенская О. О., Малышев Д. С., Дискретный анализ и исследование операций 2021 Т. 28 № 1 С. 15–47
Задача о взвешенной вершинной раскраске для заданного взвешенного графа состоит в том, чтобы минимизировать количество используемых цветов так, что для каждой вершины количество назначаемых ей цветов равно ее весу и назначаемые множества цветов для любых смежных вершин не пересекаются. Для всех наследственных классов, определяемых двумя связными 5-вершинными порожденными запретами, кроме четырех случаев, известна вычислительная сложность ...
Добавлено: 15 декабря 2020 г.
Фомин Д. Б., Математические вопросы криптографии 2020 Т. 11 № 4 С. 133–149
Исследуются параметры некоторых подстановок, основанных на конструкции типа «Бабочка», и их влияние на значение алгебраической степени подстановки и показателя дифференциальной равномерности. ...
Добавлено: 25 ноября 2020 г.