?
Некоторые полные сложностные дихотомии для задачи о доминирующем множестве
Математические заметки. 2025. Т. 117. № 1. С. 62–78.
Дахно Г. С., Malyshev D.
Publication based on the results of:
М.: Наука и технологии, 2026.
«Телекоммуникации» ежемесячный рецензируемый производственный, информационно-аналитический и учебно-методический журнал выходит в свет с июля 2000 г.
Для руководителей и работников промышленности, научно-исследовательских и проектно-конструкторских институтов, высших учебных заведений, аспирантов и студентов, а также для специалистов, разрабатывающих, выпускающих и эксплуатирующих средства телекоммуникаций.
Новости разработок и производства, прогнозы развития, защита информации, Нормативные, справочные, аналитические и учебно-методические материалы.
Переход к глобальному информационному ...
Added: July 4, 2026
МФТИ, 2025.
абота редакции научного журнала «Труды Московского физико-технического института» (кратко «Труды МФТИ»), редакционной коллегии и редакционного совета осуществляется в соответствии с Положением, утвержденным ректором института. В состав редакционной коллегии входят руководители института, факультетов, институтских и факультетских кафедр. Главный редактор журнала —президент МФТИ, член-корр. РАН Кудрявцев Н.Н.
Журнал «Труды МФТИ» входит в базу данных РИНЦ (Российский Индекс Научного Цитирования) и доступен в электронной ...
Added: July 4, 2026
Hualin M., Jie Z., Jerome Y. et al., Journal of Internet Technology 2026 Vol. 27 No. 3 P. 367–382
In open, interference-prone scenarios, the scarcity of precisely annotated signal samples limits the application of deep learning–based modulation identification, which generally relies on extensive labeled data for stability. Relation Networks, as an emerging class of deep learning models, exhibit rapid convergence in few-shot learning tasks. Motivated by the fast convergence property of relation-based learning and ...
Added: July 3, 2026
Osipov D., Информационно-управляющие системы 2026 № 3 С. 49–62
Introduction: In many communication systems under construction and those to be created power control and channel estimation techniques developed for the previous generation communication systems fail to provide desired precision. One way to solve this problem is to use order-statistics-based reception techniques that do not need channel estimation or power control. To ensure the desired ...
Added: July 3, 2026
Springer, 2026.
This book presents established and new research on the close connections between graph games and systems of logic, particularly existing and newly designed modal logics. The volume utilizes two graph games – the sabotage game and the hide-and-seek game – to demonstrate the natural interplay between designing new graph games and exploring new kinds of ...
Added: June 30, 2026
Pochinka O., Barinova M., Journal of Geometry and Physics 2026 Vol. 228 P. 1–8
In the present paper we consider an Ω-stable 3-diffeomorphism with a solid or thickened surfaced non-trivial basic set. Such basic sets include, for instance, all one-dimensional expanding attractors and those two-dimensional basic sets that are not expanding. We prove that the chain recurrent set of every such a diffeomorphism necessarily contains at least two non-trivial ...
Added: June 30, 2026
German O., Illarionov A., Известия РАН. Серия математическая 2026 Т. 90 № 3 С. 3–18
Пусть симплекс с целочисленными вершинами - содержащий ровно одну целочисленную точку, отличную от своих вершин. В работе доказывается, что если точка находится во внутренности симплекса или в относительной внутренности некоторой гиперграни симплекса, то объем симплекса ограничен величиной, зависящей только от размерности, в противном случае объем симплекса может быть сколь угодно большим. Этот результат применяется для вывода асимптотической формулы для среднего числа вершин полиэдров ...
Added: June 29, 2026
Netherlands: ScienceDirect, 2025.
No ...
Added: June 28, 2026
Kazimirov D., Vitalii Gulevskii, Kroshnin A. et al., Mathematics 2026 Article 1136
The Hough transform (HT) is widely used in computer vision, tomography, and neural networks. Numerous algorithms for HT computation have been proposed, making their systematic comparison essential. However, existing comparative methodologies are either non-universal and limited to certain HT formulations, or task-oriented, relying on application-specific criteria that do not fully capture algorithmic properties. This paper ...
Added: May 28, 2026
Dudakov S., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18
In this paper we study the problem of total derivability in context-free, noncontracting, and context-sensitive grammars. Given a grammar and a terminal word, one has to determine whether there exists a derivation of this word which uses each production no less than a given number of times. It is proved that the problem of total ...
Added: March 18, 2026
Speranski S. O., Алгебра и логика 2013 Т. 52 № 2 С. 236–254
Изучаются иерархии проблем общезначимости для префиксных фрагментов вероятностной логики с кванторами по пропозициональным формулам, обозначаемой QPL, и её вариантов. Доказывается: если подполе F вещественных чисел определимо в стандартной модели арифметики посредством формулы второго порядка, не содержащей кванторов по множествам, то проблема общезначимости над F-значными вероятностными структурами для $\Sigma_4$-QPL-предложений является $\Pi^1_1$-полной и, как следствие, соответствующая иерархия проблем общезначимости схлопывается. Более того, при ...
Added: December 27, 2025
Дахно Г. С., Malyshev D., Математические заметки 2026 Т. 119 № 3 С. 360–376
Наследственный класс — множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-ВР) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных ...
Added: November 26, 2025
Onoprienko A., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 № 527 С. 206–216
We study the algorithmic complexity of the cooperative card game Hanabi. The feature of Hanabi is that players see each other’s cards but not their own, and exchange information through hints. Even in the model with one player who has full information about the deck, Hanabi remains NP-hard. We found the minimal parameters ofthe game ...
Added: November 23, 2025
Rybakov M., Щербаков М. И., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 46–49.
Логики с аксиомой конвергентности: сложность при малом числе переменных в языке ...
Added: June 21, 2025
Kudinov A., Rybakov M., В кн.: Четырнадцатые Смирновские чтения по логике: материалы Междунар. науч. конф., Москва, 19-21 июня 2025 г.: М.: Издатель Александр Воробьев, 2025. С. 36–39.
Показано, что каждая модальная логика, содержащая классическую логику высказываний и содержащаяся в слабой логике Гжегорчика, имеет NP-трудную проблему выполнимости для константного фрагмента. В частности, константные фрагменты ненормальных модальных логик E, EM, EN и EMN являются coNP-полными. ...
Added: June 21, 2025
Sapronov Y., Yudin N., 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 ...
Added: June 10, 2025
Taletskii D., Дискретный анализ и исследование операций 2025 Т. 32 № 1 С. 122–144
Вечным доминирующим множеством графа называется доминирующее множество D, на котором располагается первоначально мобильная охрана (не более одного охранника может находиться в каждой вершине). Для любой бесконечной последовательности атак на вершины графа множество D может быть модифицировано путём передвижения охранника со смежной вершины в атакуемую вершину (предполагается, что атакуемая вершина не была занята охранником во время ...
Added: October 5, 2024
Taletskii D., Дискретный анализ и исследование операций 2024 Т. 31 № 1 С. 109–128
The set of graph vertices J_k is called k-dominating independent (k > 1) if its vertices are pairwise adjacent and every vertex not from J_k is adjacent to at least k vertices from J_k. In the presentb paper we obtain new upper bounds for the number of k-dominating independent sets for k > 2 in ...
Added: March 25, 2024
Taletskii D., Математический сборник 2023 Т. 214 № 11 С. 133–156
Сформулирована следующая гипотеза: если средняя степень вершин графа не превосходит натурального числа k ⩾ 1, то количество его k-доминирующих множеств не превосходит количества его независимых множеств, при этом равенство возможно, если и только если граф является k-регулярным. Эта гипотеза доказана для случая k ∈ {1,2}. ...
Added: November 2, 2023
G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31
A hereditary class is a set of simple graphs closed under deletion of vertices; every such class is defined by the set of its minimal forbidden induced subgraphs. If this set is finite, then the class is said to be finitely defined. The concept of a boundary class is a useful tool for the analysis ...
Added: December 6, 2022
Rybakov M., Агаджанян И. А., / arXiv. Серия 2211.14571 "Logic". 2022.
Доказывается PSPACE-трудность константных фрагментов всех логик, лежащих между K и wGrz ...
Added: December 5, 2022
Malyshev D., Дугинов О. И., Дискретный анализ и исследование операций 2022 Т. 29 № 2 С. 38–61
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы смежные рёбра были окрашены в разные цвета. Для всех классов графов, определяемых множествами запрещённых подграфов с 7 рёбрами каждый, известен сложностной статус данной задачи. В настоящей работе рассматривается случай запретов с 8 рёбрами. Нетрудно заметить, что задача о рёберной раскраске будет ...
Added: November 15, 2022
Rybakov M., Вестник Тверского государственного университета. Серия: Прикладная математика 2021 № 3 С. 5–17
The paper deals with the word problem for modal algebras. It is proved that, for the variety of all modal algebras, the word problem is PSPACEcomplete if only constant modal terms or only 0-generated modal algebras are considered. We also consider the word problem for different varieties of modal algebras. It is proved that the ...
Added: November 13, 2021
Sirotkin D., Malyshev D., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760–766
The vertex 3-colourability problem is to verify whether it is possible to split the vertex set of a given graph into three subsets of pairwise nonadjacent vertices or not. This problem is known to be NP-complete for planar graphs of the maximum face length at most 4 (and, even, additionally, of the maximum vertex degree ...
Added: June 5, 2021