?
О случаях полиномиальной разрешимости задачи о рёберной раскраске, порождаемых запрещёнными 8-рёберными субкубическими лесами
Дискретный анализ и исследование операций. 2022. Т. 29. № 2. С. 38–61.
Малышев Д. С., Дугинов О. И.
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы смежные рёбра были окрашены в разные цвета. Для всех классов графов, определяемых множествами запрещённых подграфов с 7 рёбрами каждый, известен сложностной статус данной задачи. В настоящей работе рассматривается случай запретов с 8 рёбрами. Нетрудно заметить, что задача о рёберной раскраске будет NP-трудной для такого класса, если среди его 8-рёберных запретов нет субкубического леса. В данной работе доказывается, что запрещение любого субкубического 8-рёберного леса порождает класс с полиномиальной разрешимостью задачи о рёберной раскраске, кроме случаев, образованных дизъюнктной суммой одного из четырёх лесов и пустого графа. Для всех оставшихся случаев доказывается аналогичный результат для пересечения с множеством графов максимальной степени не менее чем 4.
Абызов А. Н., Буутай П. Н., Математика и теоретические компьютерные науки 2026 Т. 4 № 2 С. 4–75
Статья носит обзорно-методический характер и посвящена развитию идей Е.И. Золотарёва, заложенных в его подходе к доказательству квадратичного закона взаимности (1872 г.). Мы рассматриваем расширения подхода Золотарёва на абстрактные числовые кольца, приведенные в работе А. Бруньята и П.Л. Кларка (2015 г.), и на конечные группы, изученные в статье У. Дьюка и К. Хопкинс (2005 г.). Также ...
Добавлено: 30 июля 2026 г.
Уилкокс П., Романов А. Ю., М.: ДМК Пресс, 2025.
Книга, которую вы держите в руках, продолжает серию «Книжная полка истового
инженера», которая издается при поддержке компании YADRO.
Данная книга представляет собой учебник по теоретическим основам продвинутой
функциональной верификации и содержит лучшие практики, используемые в настоящее
время. В ней подробно описана унифицированная методология верификации
(UVM) и раскрыты такие темы, как функциональный виртуальный прототип, функциональное
покрытие, утверждения, формальная верификация, тестбенчи, косимуляция,
эмуляция, аппаратное ...
Добавлено: 30 июля 2026 г.
Mikhaylets E. V., Razorenova A. М., Chernyshev V. L. и др., Scientific Reports 2026 Vol. 16 Article 23560
Добавлено: 29 июля 2026 г.
Попеленский Ф. Ю., Математический сборник 2026 Т. 217 № 2 С. 108–153
В недавней работе В. М. Бухштабера и автора была введена новая структура в когомологиях алгебр Хопфа в терминах спектральной последовательности Бухштабера (Bss). В классической алгебре Стинрода A2 имеется важная подалгебра Хопфа A(1), когомологии которой давно известны. В настоящей работе обсуждаемая структура на этих когомологиях полностью вычислена.
В рамках демонстрации методов Bss решена обратная задача: получено новое ...
Добавлено: 28 июля 2026 г.
Metlov K., Andrei B. Bogatyrëv, Annalen der Physik 2026 Vol. 538 No. 6 Article e70234
Добавлено: 28 июля 2026 г.
Думкин Н. А., Александров Д. В., Прозорский М. А., Труды Института системного программирования РАН 2026 Т. 38 № 1 С. 255–274
Предложен теоретически обоснованный подход к адаптивному восстановлению
видеофрагментов на стороне клиента с использованием методов машинного обучения и анализа сцены.
Метод включает формальную постановку задачи, модель конечного автомата для принятия решений,
функцию стоимости восстановления, а также новый этап в подготовке видео – оценку динамики сцены
с последующей записью признака в HLS-плейлист. Такой признак позволяет повысить точность выбора
методов восстановления фрагментов видео. ...
Добавлено: 27 июля 2026 г.
Меновщиков А. В., Ukhlov A., Rendiconti del Circolo Matematico di Palermo 2026 Vol. 75 Article 91
Добавлено: 27 июля 2026 г.
Меновщиков А. В., Journal of Mathematical Sciences 2026 Vol. 298 P. 608–618
Добавлено: 27 июля 2026 г.
Cham: Springer, 2026.
Добавлено: 26 июля 2026 г.
Добавлено: 23 июля 2026 г.
Писляков В. В., Вестник Томского государственного университета. Филология 2026 № 101 С. 175–192
Исследуется использование паремий в статьях, опубликованных в отечественных научных журналах. В результате поиска по платформе eLIBRARY.RU и постатейного просмотра полных текстов формируется «паремический массив» – набор журнальных статей, вышедших за 2014–2023 гг., в которых встречается одна из десяти исследуемых пословиц. Выделяются только случаи, когда пословицы используются авторами как пришедшиеся к слову изречения, а не как ...
Добавлено: 22 июля 2026 г.
Association for Computing Machinery (ACM), 2026.
Добавлено: 22 июля 2026 г.
Korogod D., Shapeev A., Ivan S. Novikov, Physical Review B: Condensed Matter and Materials Physics 2026 Vol. 114 No. 2 Article 024104
Добавлено: 22 июля 2026 г.
Sozykin K., Rybin N., Chertkov A. и др., Physical Review B: Condensed Matter and Materials Physics 2026 Vol. 113 No. 22 Article 224111
Добавлено: 22 июля 2026 г.
Веретенников А. Ю., Pascucci A., Rondelli A., Stochastic Processes and their Applications 2026 Vol. 199 Article 104978
Добавлено: 17 июля 2026 г.
Веретенников А. Ю., Ляппиева А. А., Теория вероятностей и ее применения 2026 Т. 71 № 2 С. 295–304
Установлен новый результат о сильной единственности для многомерного СДУ с невырожденной диффузией и частично нерегулярным сносом. Его можно рассматривать как комбинированный вариант на темы Ямада и Ватанабэ (1971), Звонкина (1974) и первого автора настоящей статьи (1980). ...
Добавлено: 17 июля 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 г.