?
Некоторые классификации сложности задачи о вершинной 3-раскраске
Математические заметки. 2026. Т. 119. № 3. С. 360–376.
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных классов, определяемых 5-вершинными порожденными запретами.
В данной работе для задачи 3-ВР рассматривается вопрос о полной классификации алгоритмической сложности для пар порожденных запретов с 6 вершинами. Известно, что задача 3-ВР будет NP-полной для такого класса, если ни один элемент пары не будет лесом, и что она будет полиномиальной разрешимой, если один из запретов является линейным лесом. В этой работе рассмотрены четыре нелинейных 6-вершинных леса и получены классификации сложности задачи 3-ВР для всех соответствующих пар.
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Lerman L. M., Turaev D. V., Regular and Chaotic Dynamics 2026 Vol. 31 No. 3 P. 349–369
Добавлено: 15 мая 2026 г.
Добавлено: 15 мая 2026 г.
Добавлено: 15 мая 2026 г.
Лебедев В. В., Journal of Mathematical Analysis and Applications 2026 Vol. 563 No. 2 Article 130787
Добавлено: 14 мая 2026 г.
Blokh A., Oversteegen L., Selinger N. и др., Arnold Mathematical Journal 2025 Vol. 12 No. 1 P. 1–40
Добавлено: 13 мая 2026 г.
Петров И. В., Автоматика и телемеханика 2026 № 6 С. 82–118
Системам связанных агентов и сетевому управлению посвящено большое число отечественных и зарубежных исследований. Исторически, наибольший интерес в теории управления возникал к усредняющим системам и, в частности, к задаче консенсуса. Однако сетевое взаимодействие может характеризоваться более специфическими функциями, отражающими зависимость от действий соседей по сети, что особенно явно проявляется в моделях стратегического взаимодействия на сети, которое ...
Добавлено: 12 мая 2026 г.
М.: ООО «Макс Пресс», 2026.
В настоящем сборнике представлены тезисы докладов участников семинара "Интеграция основного и дополнительного физико-математического образования", проходившего 11 февраля 2026 года в ГБОУ Школа №2007 ФМШ г. москвы, а также другие публикации, посвящённые вопросам дополнительного физико-математического образования. ...
Добавлено: 11 мая 2026 г.
Novikov R., Сивкин В. Н., Inverse Problems 2026 Vol. 42 No. 4 Article 045009
Добавлено: 11 мая 2026 г.
Hecht M., Hofmann P., Wicaksono D. и др., IMA Journal of Numerical Analysis 2026 Vol. 00 P. 1–30
Добавлено: 11 мая 2026 г.
Белоусов Н. М., Черепанов Л. К., Деркачов С. Э. и др., Selecta Mathematica, New Series 2026 Vol. 32 Article 44
Добавлено: 6 мая 2026 г.
Цыганов А. В., Порубов Е. О., Теоретическая и математическая физика 2026 Т. 227 № 2 С. 336–355
Теория тензорных инвариантов обыкновенных дифференциальных уравнений и классификация Картана простых алгебр Ли используется для установления изоморфизма задачи Козлова о движении ферромагнетика в магнитном поле и задачи Шоттки о движении четырехмерного твердого тела. Найдены новые полиномиальные и рациональные бивекторы Пуассона, инвариантные либо относительно пары коммутирующих фазовых потоков, либо относительно одного из пары потоков. ...
Добавлено: 5 мая 2026 г.
Монахова Э. А., Монахов О. Г., Рзаев Э. Р. и др., Прикладная дискретная математика 2026 Т. 71 С. 112–127
В настоящей работе исследовано совместное конструирование топологий семейств оптимальных по диаметру циркулянтных сетей $C(N; \pm 1, \pm s_2)$ и реализуемых для них оптимальных алгоритмов маршрутизации сложности $O(1)$. Предлагаемый алгоритм маршрутизации основан на использовании масштабируемых параметров $L$-образных шаблонов плотной укладки графов на плоскости для семейств оптимальных сетей.
Определены аналитические формулы зависимости этих параметров от диаметра графов семейств ...
Добавлено: 4 мая 2026 г.
Дудаков С. М., Lobachevskii Journal of Mathematics 2025 Vol. 46 No. 12 P. 6092–6102
Добавлено: 1 мая 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 г.
Оноприенко А. А., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 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 г.