?
Сложность проблемы равенства слов в многообразиях модальных алгебр
Вестник Тверского государственного университета. Серия: Прикладная математика. 2021. № 3. С. 5–17.
Приводится доказательство PSPACE-полноты проблемы равенства слов в классе всех нуль-порождённых модальных алгебр, или, эквивалентно, проблемы равенства константных слов в классе всех модальных алгебр. Также рассматривается вопрос о сложности равенства слов в произвольном многообразии модальных алгебр. Доказывается, что уже проблема равенства константных слов в многообразии модальных алгебр может быть сколь угодно трудной (включая как классы сложности, так и степени неразрешимости). Показано, как построить соответствующие многообразия.
Добавлено: 8 ноября 2026 г.
Ретинский В. И., Функциональный анализ и его приложения 2026 Т. 60 № 4 С. 83–100
Приведено обобщение матричной теоремы о деревьях на случай перечисления пар остовных деревьев. Это обобщение включает в качестве частных случаев и унифицирует сразу несколько известных ранее результатов, в частности классическую теорему Кирхгофа, теорему Масбаума–Вайнтроба о перечислении 3-деревьев, а также аналог матричной теоремы о деревьях для перечисления 4-элементов Кирхгофа. ...
Добавлено: 5 ноября 2026 г.
Левашев В. А., Математические заметки 2026 Т. 120 № 5 С. 843–846
Пусть 𝐴 – коммутативное ассоциативное кольцо с единицей и 𝐴((𝑡)) = 𝐴[[𝑡]][𝑡−1] – кольцо рядов Лорана над 𝐴. Алгебра 𝐴((𝑡)) имеет естественную топологию, где 𝐴 – подмодули вида 𝑡𝑚𝐴[[𝑡]] образуют базу окрестностей нуля. Пусть также Ω1𝐴((𝑡))/𝐴 – модуль кэлеровых 1-дифференциалов 𝐴((𝑡)) над 𝐴. ...
Добавлено: 5 ноября 2026 г.
Алексеев О. В., Letters in Mathematical Physics 2026 Vol. 116 No. 5 Article 132
Добавлено: 5 ноября 2026 г.
Левин А. М., Сахарова Н. Е., / Series arXiv "math". 2024. No. 2412.17795.
Добавлено: 4 ноября 2026 г.
Жужома Е. В., Медведев В. С., Regular and Chaotic Dynamics 2026 Vol. 31 No. 5 P. 732–742
Добавлено: 3 ноября 2026 г.
Добавлено: 3 ноября 2026 г.
Жужома Е. В., Zhirov A. Y., Russian Journal of Nonlinear Dynamics 2026 Vol. 22 No. 2 P. 403–414
Добавлено: 3 ноября 2026 г.
Elena R. Loubenets, Sergey Kuznetsov, Quantum Information Processing 2026 Vol. 25 Article 358
Добавлено: 3 ноября 2026 г.
Добавлено: 3 ноября 2026 г.
Добавлено: 2 ноября 2026 г.
Смирнов С. В., Дынников И. А., Успехи математических наук 2002 Т. 57 № 6 С. 183–184
Изучаются точно решаемые циклические q-цепочки Дарбу, обобщающие q-осциллятор ...
Добавлено: 1 ноября 2026 г.
Смирнов С. В., Алгебра и анализ 2003 Т. 15 № 5 С. 228–253
В работе построен дискретный q-аналог одевающей цепочки Веселова–Шабата (являющейся обобщением гармонического осциллятора). Показано, что, как и в непрерывном случае, соответствующие операторные соотношения позволяют полностью определить дискретный спектр операторов цепочки: в данном случае он состоит из нескольких q-арифметических прогрессий. В этой работе удалось реализовать циклическую q-цепочку ограниченными разностными самосопряженными операторами, причем спектр каждого из них дискретен, а собственные векторы образуют ...
Добавлено: 1 ноября 2026 г.
Смирнов С. В., Теоретическая и математическая физика 2012 Т. 172 № 3 С. 387–402
Изучаются интегрируемые условия обрыва для полудискретной цепочки Тоды. Построено представление Лакса для полудискретного аналога цепочек, соответствующих простым алгебрам Ли серии C. Введены нелокальные переменные, в терминах которых записываются симметрии бесконечной полудискретной цепочки, и классифицируются условия обрыва определенного вида, совместимые с симметриями бесконечной цепочки. ...
Добавлено: 1 ноября 2026 г.
Пиле Я. Э., Щур Л. Н., Nuclear Physics B 2026 No. 0550-3213 Article 117706
Добавлено: 1 ноября 2026 г.
Борзых Д. А., Орлов Н. А., Экономический журнал Высшей школы экономики 2026 Т. 30 № 3 С. 457–486
Работа посвящена сравнению двух методов оценивания модели стохастической волатильности (SV-модели) – методу максимального квазиправдоподобия (QML) и методу Монте-Карло с цепями Маркова (MCMC). Сравнение
проводится как на симулированных, так и на реальных данных. На симулированных данных метод MCMC показывает значительно более точные результаты. При этом с точки зрения вычислений QML-метод имеет гораздо
более высокое быстродействие и требует существенно ...
Добавлено: 29 октября 2026 г.
Guerreiro I., Sergey Skorokhod, di Volo M. и др., Communications in Nonlinear Science and Numerical Simulation 2027 Vol. 164 Article 110954
Добавлено: 29 октября 2026 г.
Добавлено: 27 октября 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 г.