?
О случаях полиномиальной разрешимости задачи о рёберной раскраске, порождаемых запрещёнными 8-рёберными субкубическими лесами
Дискретный анализ и исследование операций. 2022. Т. 29. № 2. С. 38–61.
Малышев Д. С., Дугинов О. И.
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы смежные рёбра были окрашены в разные цвета. Для всех классов графов, определяемых множествами запрещённых подграфов с 7 рёбрами каждый, известен сложностной статус данной задачи. В настоящей работе рассматривается случай запретов с 8 рёбрами. Нетрудно заметить, что задача о рёберной раскраске будет NP-трудной для такого класса, если среди его 8-рёберных запретов нет субкубического леса. В данной работе доказывается, что запрещение любого субкубического 8-рёберного леса порождает класс с полиномиальной разрешимостью задачи о рёберной раскраске, кроме случаев, образованных дизъюнктной суммой одного из четырёх лесов и пустого графа. Для всех оставшихся случаев доказывается аналогичный результат для пересечения с множеством графов максимальной степени не менее чем 4.
Association for Computational Linguistics, 2026.
Добавлено: 14 июня 2026 г.
Strube M., Braud C., Hardmeier C. и др., Suzhou: Association for Computational Linguistics, 2025.
Добавлено: 11 июня 2026 г.
Добавлено: 10 июня 2026 г.
Добавлено: 10 июня 2026 г.
Дистиллированные кисломолочные напитки встречаются в пищевой промышленности редко, несмотря на повсеместное распространение растительных спиртных напитков. В настоящее время производство крепких дистиллированных алкогольных напитков из кисломолочных продуктов с использованием традиционных технологий известно лишь среди монголоязычных народов и их сибирских соседей. Данное исследование представляет собой первый междисциплинарный анализ дарасуна, традиционного бурятского спиртного напитка, изготавливаемого из кисломолочного напитка ...
Добавлено: 10 июня 2026 г.
Butorova A., Bobakov V., Sergeev A. и др., European Physical Journal: Special Topics 2026 P. 1–19
Добавлено: 10 июня 2026 г.
Добавлено: 28 мая 2026 г.
Дудаков С. М., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 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 г.
Рыбаков М. Н., Вестник Тверского государственного университета. Серия: Прикладная математика 2021 № 3 С. 5–17
Приводится доказательство PSPACE-полноты проблемы равенства слов в классе всех нуль-порождённых модальных алгебр, или, эквивалентно, проблемы равенства константных слов в классе всех модальных алгебр. Также рассматривается вопрос о сложности равенства слов в произвольном многообразии модальных алгебр. Доказывается, что уже проблема равенства константных слов в многообразии модальных алгебр может быть сколь угодно трудной (включая как классы сложности, ...
Добавлено: 13 ноября 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 г.
Gillis N., Шитов Я. Н., Linear Algebra and its Applications 2019 Vol. 581 P. 367–382
Добавлено: 11 ноября 2020 г.