?
Сложность проблемы равенства слов в многообразиях модальных алгебр
Вестник Тверского государственного университета. Серия: Прикладная математика. 2021. № 3. С. 5–17.
Приводится доказательство PSPACE-полноты проблемы равенства слов в классе всех нуль-порождённых модальных алгебр, или, эквивалентно, проблемы равенства константных слов в классе всех модальных алгебр. Также рассматривается вопрос о сложности равенства слов в произвольном многообразии модальных алгебр. Доказывается, что уже проблема равенства константных слов в многообразии модальных алгебр может быть сколь угодно трудной (включая как классы сложности, так и степени неразрешимости). Показано, как построить соответствующие многообразия.
Mysin I. E., Dubrovin S. V., Cognitive Neurodynamics 2026 Vol. 20 No. 191 P. 1–30
Добавлено: 14 ноября 2026 г.
Ермолаев Е. С., Чернышев В. Л., Скрипченко А. С., Journal of Nonlinear Science 2026 Vol. 36 No. 122 (2026) P. 1–37
We study upper bounds for the moment of permanent -saturation in finite metric graphs. The dynamics is generated by moving points travelling with unit speed along edges and branching into all outgoing directions whenever they reach a vertex. We first reformulate this branched dynamics in terms of birth times at vertices and prove a sufficient ...
Добавлено: 12 ноября 2026 г.
Alfimov Mikhail, Kurakin Andrey, Journal of High Energy Physics 2026 Vol. 2026 Article 99
Добавлено: 12 ноября 2026 г.
Шехтман В. Б., Shkatov D., Review of Symbolic Logic 2026 Vol. 19 No. 4 P. 859–882
Добавлено: 12 ноября 2026 г.
Игнатьев М. В., Вилкин Т. В., Mediterranean Journal of Mathematics 2026 Vol. 23 No. 2 Article 70
Добавлено: 12 ноября 2026 г.
Максаев А. М., Промыслов В. В., Тишутин П. С., Записки научных семинаров ПОМИ РАН 2026 Т. 554 С. 218–235
Пусть K — алгебраически замкнутое поле, а ℰₖ — множество n × n матриц над K, имеющих ровно k различных собственных значений. Ранее классификация линейных отображений T: Mₙ(K) → Mₙ(K), удовлетворяющих условию T(ℰₙ) ⊆ ℰₙ, была получена для обратимых отображений над полем характеристики 0. В данной работе эта классификация распространяется на произвольные, в том числе ...
Добавлено: 11 ноября 2026 г.
Баринова М. К., Tirskaya Karina, Владикавказский математический журнал 2026 Vol. 28 No. 3 P. 25–43
В работе исследуется проблема существования энергетической функции для дискретных динамических систем, заданных структурно устойчивыми диффеоморфизмами на гладких, компактных, ориентируемых поверхностях без края. Для рассматриваемого класса такая функция определяется как непрерывная функция, убывающая вдоль орбит системы вне неблуждающего множества и постоянная на неблуждающих орбитах. На данный момент известно, что если неблуждающее множество структурно устойчивого диффеоморфизма поверхности ...
Добавлено: 11 ноября 2026 г.
Илларионов А. А., Математический сборник 2026 Т. 217 № 11 С. 56–87
Пусть $b(\alpha;T)$ --- количество наилучших совместных диофантовых приближений с общим знаменателем $\le T$ к точке $\alpha \in {\Bbb R}^n$.
Мы выводим асимптотические формулы для среднего значения этой величины (усреднение проводится по всем рациональным точкам вида $\alpha = (k_1/N,\ldots, k_n/N)$, $N\le R$), а также для ее математического ожидания
при условии, что $\alpha$ равномерно распределена на кубе $[0,1)^n$. ...
Добавлено: 10 ноября 2026 г.
Верещагин Н. К., Математический сборник 2026 Т. 217 № 10 С. 3–46
Теорема Гудмана-Штрауса утверждает, что для “почти всякой” подстановки семейство подстановочных замощений софично, т.е. может быть задано локальными правилами для некоторой раскраски плиток. Условия на подстановку, гарантирующие софичность, довольно сложные.
В настоящей работе мы предлагаем версию теоремы Гудмана-Штрауса с более простыми условиями на подстановку. Хотя эти условия достаточно ограничительны, мы показываем, что в сочетании с двумя простыми приемами (взятием достаточно ...
Добавлено: 10 ноября 2026 г.
Добавлено: 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 г.
Добавлено: 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 г.