?
NP-полнота игры “Ханаби” при минимальных параметрах
Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика). 2025. № 527. С. 206–216.
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае дальнейшего уменьшения этих параметров игра оказывается разрешимой за полиномиальное время.
Ключевые слова: вычислительная сложностьalgorithmic game theoryалгоритмическая теория игрNP-полнота NP-completenesscomputational complexityHanabiХанаби
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
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 г.
Иванашев Я. М., , in: 19th Annual Conference, TAMC 2025, Jinan, China, September 19–21, 2025, Proceedings. Theory and Applications of Models of Computation. Lecture Notes in Computer Science (LNCS, volume 16084)Vol. 16084.: Springer, 2026. P. 15–24.
Добавлено: 20 января 2026 г.
Odintsov S., Сперанский С. О., Logic and Logical Philosophy 2012 Vol. 21 No. 3 P. 209–228
The present paper is devoted to computational aspects of propositional inconsistency-adaptive logics. In particular, we prove (relativized versions of) some principal results on computational complexity of derivability in such logics, namely in cases of CLuN-r and CLuN-m , i.e., CLuN supplied with the reliability strategy and the minimal abnormality strategy, respectively. ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., Studia Logica 2013 Vol. 101 No. 6 P. 1237–1262
In a rather general setting, we prove a number of basic theorems concerning computational complexity of derivability in adaptive logics. For that setting, the so-called standard format of adaptive logics is suitably adopted, and the corresponding completeness results are established in a very uniform way. ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., Archive for Mathematical Logic 2013 Vol. 52 No. 5–6 P. 507–516
We carry out a study of definability issues in the standard models of Presburger and Skolem arithmetics (henceforth referred to simply as Presburger and Skolem arithmetics, for short, because we only deal with these models, not the theories, thus there is no risk of confusion) supplied with free unary predicates — which are strongly related to definability in ...
Добавлено: 27 декабря 2025 г.
Дахно Г. С., Малышев Д. С., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Добавлено: 26 ноября 2025 г.
Мельман А. С., Джанашиа К. М., Евсютин О. О., Computer Standards and Interfaces 2026 Vol. 96 Article 104066
Добавлено: 3 сентября 2025 г.
Рыбаков М. Н., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...
Добавлено: 21 июня 2025 г.