• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Articles
  • On Universality of Regular Realizability Problems
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
September 11, 2026
How to Assess Students Knowledge in the Age of AI
A researcher at HSE University has proposed a flowchart to help lecturers decide how to assess students who use artificial intelligence. It shows where the use of AI should be restricted and where it can be incorporated into the learning process. The article has been published in IT Professional.
September 9, 2026
‘Balkan Hospitality Opens Doors: Studying Dialects on the Verge of Extinction
You cannot study spoken dialects from books. Instead, you need to go to a village, seek out its elders, and earn the trust of local residents before you can record hours of spontaneous stories. This is how Natalia Muravleva, Associate Professor at the Faculty of Humanities, conducts her research. Her internship in Serbia continued her long-standing study of dialects spoken by Macedonian settlers. In this interview, she discusses how diaspora cultural centres help researchers reach informants, why native speakers need to be interviewed only in their own language (otherwise, as she puts it, they may 'break'), and how a single field season helped her finalise her monograph. She also shares warm memories of autumn in Belgrade and of colleagues with whom grammar can be discussed in three languages at once.
September 9, 2026
Scientists Train Neural Network to Generate Process Plans from 3D Models
Researchers at the HSE FCS AI and Digital Science Institute have developed CAD2TechSpec, a framework that converts 3D models of mechanical parts into machining process plans—step-by-step instructions for machine tools. The solution aims to reduce the time required for the design and preparation of technical process documentation in mechanical engineering, aircraft manufacturing, and other high-tech industries. The study findings have been published in PeerJ Computer Science.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

On Universality of Regular Realizability Problems

Problems of Information Transmission. 2024. Vol. 60. P. 209–232.
A. A. Rubtsov, M. N. Vyalyi

We prove the universality of the regular realizability problem for several classes of filters. These filters are descriptions of finite relations on the set of nonnegative integers in the format proposed by P. Wolf and H. Fernau. The universality is proved with respect to the disjunctive reduction in polynomial time for unary relations and in polynomial space for invariant binary relations. The necessity of stronger reductions corresponds to the results of Wolf and Fernau on the decidability of regular realizability problems for many algorithmic problems in graph theory.

Research target: Computer Science Mathematics
Language: English
DOI
Text on another site
Keywords: reductionNP-oracleregular realizability
Similar publications
Характеристические алгебры и интегрируемые системы экспоненциального типа
Смирнов С. В., Миллионщиков Д. В., Уфимский математический журнал 2021 Т. 13 № 2 С. 44–73
В данной работе изучаются характеристические алгебры для систем экспоненциального типа, соответствующих вырожденным матрицам Картана. Эти системы обобщают хорошо известные в теории интегрируемых систем гиперболические уравнения синус-Гордон и Цицейки. Для таких систем, соответствующих матрицам Картана ранга 2, характеристические алгебры описаны явно в терминах образующих и соотношений, и доказано, что они имеют линейный рост. Исследуется связь между ...
Added: September 11, 2026
Darboux formulae for linear hyperbolic equations in the discrete case
Смирнов С. В., Glasgow Mathematical Journal 2026 Vol. 68 No. 2 P. 299–316
In the second half of the 19th century Darboux obtained determinant formulae that provide the general solution for a linear hyperbolic second order PDE with finite Laplace series. These formulae played an important role in his study of the theory of surfaces and, in particular, in the theory of conjugate nets. During the last three ...
Added: September 11, 2026
Integral preserving discretization of 2D Toda lattices
Смирнов С. В., Journal of Physics A: Mathematical and Theoretical 2023 Vol. 56 No. 26 Article 265204
There are different methods of discretizing integrable systems. We consider semi-discrete analog of two-dimensional Toda lattices associated to the Cartan matrices of simple Lie algebras that was proposed by Habibullin in 2011. This discretization is based on the notion of Darboux integrability. Generalized Toda lattices are known to be Darboux integrable in the continuous case ...
Added: September 11, 2026
ВЕРОЯТНОСТНЫЕ МОДЕЛИ РАЗМЕЩЕНИЯ ПО ЯЧЕЙКАМ СЛУЧАЙНОГО ЧИСЛА ЧАСТИЦ
Enatskaya N., Труды Карельского научного центра РАН. Серия 10: Математическое моделирование и информационные технологии 2026 № 6 С. 132–138
In schemes S for placing r particles in n distinguishable cells, their placement in selected m cells – schemes S∗ is studied, for which the analysis is carried out by a new enumerative method (EM) in extended areas of enumerative combinatorics: finding the number of outcomes and, based on the construction of a model of ...
Added: September 11, 2026
КОМБИНАТОРНЫЙ АНАЛИЗ СХЕМ РАЗМЕЩЕНИЯ ЧАСТИЦ С ЗАДАННЫМ МАКСИМАЛЬНЫМ УРОВНЕМ ЗАПОЛНЕНИЯ ЯЧЕЕК
Enatskaya N., Труды Карельского научного центра РАН. Серия 10: Математическое моделирование и информационные технологии 2026 № 6 С. 139–147
The class of particle cell arrangements under consideration is characterized by the introduction of an upper limit on the filling levels of the cells, which must be achieved in at least one cell of each outcome of each arrangement. The circuits are distinguished by the paired qualities of their constituent elements (cells and particles) according ...
Added: September 11, 2026
Метод кодирования голосового источника турбулентного типа на основе гибридной модели линейного предсказания
Савченко В. В., Savchenko L., Измерительная техника 2026 Т. 75 № 3 С. 105–113
Within the framework of a current area of research in the field of speech acoustics – non-invasive analysis of speech production processes – the acute problem of insufficient accuracy of parametric methods for coding a turbulent (noise) type voice source is considered. In order to overcome this problem, a method for coding a sound source with increased ...
Added: September 11, 2026
What Do Text-to-Image Models Know About the Languages of the World?
Фирсанова В. И., Journal of Mathematical Sciences 2024 Vol. 285 No. 1 P. 112–125
Text-to-image models use user-generated prompts to produce images. Such text-to-image models as DALL-E 2, Imagen, Stable Diffusion, and Midjourney can generate photorealistic or similar to human-drawn images. Apart from imitating human art, large text-to-image models have learned to produce combinations of pixels reminiscent of captions in natural languages. For example, a generated image might contain ...
Added: September 9, 2026
Многокритериальные задачи с упорядоченными по важности группами критериев (II). Решающие правила
Podinovskiy V. V., Нелюбин А. П., Автоматика и телемеханика 2026 № 8 С. 110–123
Для многокритериальных задач принятия решений по аналогии с качественной вероятностью введены понятия полной и частичной качественной важности как бинарных отношений, обладающих постулируемыми свойствами. Предложено новое определение отношения нестрогого предпочтения на множестве вариантов решений, порождаемое качественной важностью. Исследованы его свойства. Указаны аналитические правила, позволяющие попарно сравнивать варианты по предпочтительности. Проведено сравнение новых отношений предпочтения с разработанными ранее для задач, ...
Added: September 9, 2026
Теоретические основы и методы анализа решений в условиях неопределенности при качественных оценках вероятностей и предпочтений
Podinovskiy V. V., Нелюбин А. П., Автоматика и телемеханика 2026 № 7 С. 113–126
Рассматриваются задачи принятия решений, когда предпочтения оцениваются в порядковой шкале, а возможности реализации значений неопределенного фактора описываются качественной вероятностью (полной или только частичной). Вводятся определения отношений предпочтения и безразличий на множестве стратегий. Предлагаются простые решающие правила, позволяющие сравнивать стратегии по предпочтительности, и приводятся иллюстративные примеры. ...
Added: September 9, 2026
Разработка интерфейса виртуального ассистента преподавателя на основе технологий вызова функций и инженерии инструкций для больших языковых моделей
Фирсанова В. И., Человек: образ и сущность. Гуманитарные аспекты 2025 Vol. 2 No. 62 P. 203–214
Abstract. The paper highlights prompt engineering in academic setting to reduce plagiarism and increase students' interest. The research problem is the lack of a unified methodology for using artificial intelligence in education. The paper aims to create a generative artificial intelligence user interface, the Virtual Teaching Assistant. Teachers were interviewed, the first collection of presets ...
Added: September 9, 2026
Degree-based topological co-indices for QSPR modelling of benzenoid hydrocarbons: a comparative computational study
Chemical Papers 2026
Benzenoid hydrocarbons are structurally regular aromatic compounds, which makes them well suited for quantitative structure–property relationship (QSPR) studies. This study presents a QSPR analysis of nineteen benzenoid hydrocarbon species using degree-based topological co-indices. We developed a Python program to compute eleven degree-based topological co-indices from molecular graphs and evaluated their ability to explain variations in ...
Added: September 8, 2026
On phase-lock area parquet in a special slow-fast limit of model of Josephson junction.
Glutsyuk A., / Series arXiv "math". 2026.
B.Josephson (Nobel Prize, 1973) predicted a tunnelling effect for a system of two superconductors separated by a narrow dielectric (such a system is called Josephson junction): existence of a supercurrent through it and equations governing it. The overdamped Josephson junction is modeled by the family of differential equations on the 2-torus, dθdτ=1ω(cosθ+B+Acosτ), which is known as ...
Added: September 8, 2026
On exotic rationally integrable dual billiards I. Complex geometry and type of dynamics.
Glutsyuk A., / Series arXiv "math". 2026.
A planar dual billiard is a planar curve γ equipped with a family (σP)|P∈γ of projective involutions of the projective lines LP tangent to γ at P that fix P. A dual billiard is called rationally integrable, if there exists a rational function R(x,y) of two variables (called first integral) whose restriction to each tangent ...
Added: September 8, 2026
Dynamical systems on torus related to general Heun equations: phase-lock areas and constriction breaking
Alexandrov A., Glutsyuk A., Journal of Differential Equations 2026 Vol. 465 Article 114178
The overdamped Josephson junction in superconductivity theory can be modeled by the family of dynamical systems on the torus, which is known as the RSJ model. This family admits an equivalent description by a family of second-order differential equations: special double confluent Heun equations. In the present paper, we construct two new families of dynamical systems on ...
Added: September 8, 2026
On rationally integrable planar dual and projective billiards
Glutsyuk A., Inventiones Mathematicae 2026 Vol. 245 P. 977–1058
A caustic of a strictly convex planar bounded billiard is a smooth curve whose tangent lines are reflected from the billiard boundary to its tangent lines. The famous Birkhoff Conjecture, studied by many mathematicians, states that if the billiard boundary has an inner neighborhood foliated by closed caustics, then it is an ellipse. In the paper we study ...
Added: September 8, 2026
Анализ согласованности голосования стран ЕАЭС и ОДКБ в ГА ООН с помощью иерархической кластеризации
Вохминцев И. В., Вестник международных организаций: образование, наука, новая экономика 2026 Т. 21 № 2
The EAEU and the CSTO are Russia’s principal regional international organisations. Understanding, assessing, and analysing the foreign-policy positions of the countries that belong to them is a matter of the state’s national interests. This determines the purpose of the study: to identify the level and the form of cohesion in the voting of EAEU and ...
Added: September 7, 2026
Rational p-adic Hodge theory for d-de Rham-proper stacks
Prikhodko Artem, Kubrak D., Compositio Mathematica 2026 Vol. 162 No. 6 P. 1377–1438
In this follow-up paper we show that smooth Hodge-proper stacks over O𝐾 are ℚ𝑝-locally acyclic: namely the natural map between étale ℚ𝑝-cohomology of the algebraic and Raynaud generic fibers is an equivalence. This establishes the ℚ𝑝-case of general conjectures made in D. Kubrak and A. Prikhodko [p-adic Hodge theory for Artin stacks, Mem. Amer. Math. ...
Added: September 7, 2026
Lower Bounds on the Measure of the Support of Positive and Negative Parts of Trigonometric Polynomials
Ismailov A., Constructive Approximation 2026
The measure of the positivity set {x ∈ [0; 2π] | f (x) > 0} of a trigonometric polynomial f  is bounded from below by the Motzkin density. We generalize the bound to polynomials in several variables and almost periodic functions. We then use these generalizations to extend known results on Taikov’s problem. ...
Added: September 7, 2026
Pupillometry and autonomic nervous system responses to cognitive load and false feedback: an unsupervised machine learning approach
Alshanskaia E., Portnova G., Liaukovich K. et al., Frontiers in Neuroscience 2024 Vol. 18
Added: September 7, 2026
Tandem, Catalyst-Free C−C Synthesis of Nitriles from Aldehydes and Methyl Cyanoacetate with Sodium Hypophosphite
Korochantsev V., Artemy Fatkulin, Podyacheva E. et al., European Journal of Organic Chemistry 2024 Vol. 28 No. 4 Article e202401108
Saturated carbon chain elongation is a common refrain in numerous synthetic pathways. While the formation of C-C single bonds is of primary importance in organic synthesis, simultaneous introduction of functional groups such as nitrile or ester can reasonably increase its practical utility to prepare multifunctional products. Knoevenagel reaction is one of the powerful tools to ...
Added: January 23, 2025
Alkyl formates as reagents for reductive amination of carbonyl compounds
Afanasyev O., Cherkashchenko I., Kuznetsov A. et al., Mendeleev Communications 2020 Vol. 30 No. 1 P. 112–113
Alkyl formates in the presence of basic additives can serve as a reagent in the direct reductive amination of carbonyl compounds. The developed procedure can be applied to various aldehydes and ketones with electron donating and electron withdrawing groups. ...
Added: October 14, 2024
Правовые и биоэтические аспекты использования экспериментальных животных в научных целях
Лебедева Д. А., Щеглов Ю. А., Токсикологический вестник 2020 № 5 С. 10–15
This work scrutinizes modern bioethical concepts of the use of animals for scientific purposes, as well as legal aspects of its use. Initially, the authors present a brief excursion into the history of bioethics and then focus on the modern concept of ethical attitude to the animals used for scientific purposes. The authors analyze the EU Directive on ...
Added: May 18, 2024
Catalytic Utilization of Converter Gas – An industrial Waste for the Synthesis of Pharmaceuticals
Runikhina S., Afanasyev O., Kuchuk E. et al., Chemical Science 2023 Vol. 14 P. 4346–4350
Converter gas is a large scale waste product that is usually burned to carbon dioxide and contributes to the world emission of greenhouse gases. Herein we demonstrate that instead of burning the converter gas can be used as a reducing agent in organic reactions to produce valuable pharmaceuticals and agrochemicals. In particular, amide-based selected drug ...
Added: August 11, 2023
Extensions of vertex algebras. Constructions and applications
Feigin B. L., Russian Mathematical Surveys 2017 Vol. 72 No. 4 P. 707–763
This paper discusses the main known constructions of vertex operator algebras. The starting point is the lattice algebra. Screenings distinguish subalgebras of lattice algebras. Moreover, one can construct extensions of vertex algebras. Combining these constructions gives most of the known examples. A large class of algebras with big centres is constructed. Such algebras have applications ...
Added: November 5, 2020
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit