| Генерический алгоритм для проблемы вхождения в полугруппах целочисленных матриц | |
| Рыбалов Александр Николаевич1 | |
| 1.1Институт математики им. С.Л. Соболева СО РАН | |
| Дата поступления 2020.07.20 | Аннотация. В 2003 г. И. Капович, А. Мясников, В. Шпильрайн и П. Шупп предложили генерический подход к теории вычислимости и вычислительной сложности. В рамках этого подхода алгоритмическая проблема рассматривается не на всем множестве входов, а на некотором подмножестве почти всех входов. В данной статье доказывается генерическая разрешимость проблемы вхождения и проблемы умирающих матриц для полугрупп целочисленных матриц произвольного порядка. |
| Ключевые слова математика, генерическая сложность, полугруппа матриц, проблема вхождения | |
Библиография 1. Михайлова К. А. Проблема вхождения для прямых произведений групп // Матем. сб. 1966. Т. 70 (112), № 2. С. 241–251. 2. Paterson M. S. Unsolvability in 3 × 3 Matrices // Studies in Applied Mathematics. 1970. Vol. 49, № 1. P. 105– 107. 3. Halava V., Harju T. Mortality in Matrix Semigroups // The American Mathematical Monthly. 2001. Vol. 108, № 7. P. 649–653. 4. Kapovich I., Myasnikov A. G., Schupp P., Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. Vol. 264, № 2. P. 665–694. 5. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. М. : Наука, 1982. 288 с. 6. Stewart C. On divisors of Lucas and Lehmer numbers // Acta Mathematica. 2013. Vol. 211, № 2. P. 291–314. | |
Сведения о финансировании и благодарности Работа поддержана программой фундаментальных научных исследований СО РАН I.1.1.4, проект 0314-2019-0004 | |
| A generic algorithm for the membership problem in the semigroups of integer matrices | |
| Rybalov Alexander Nikolaevich 1 | |
| 1.1Sobolev Institute of Mathematics SB RAS | |
| Received 2020.07.20 | Abstract. Generic-case approach to algorithmic problems was suggested by A. Miasnikov, I. Kapovich, P. Schupp and V. Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In this paper we prove generic decidability of the membership problem and the mortality problem for semigroups of integer matrices of arbitrary order. |
| Keywords mathematics, generic computability, matrix semigroups, membership problem | |
References 1. Михайлова К. А. Проблема вхождения для прямых произведений групп // Матем. сб. 1966. Т. 70 (112), № 2. С. 241–251. 2. Paterson M. S. Unsolvability in 3 × 3 Matrices // Studies in Applied Mathematics. 1970. Vol. 49, № 1. P. 105– 107. 3. Halava V., Harju T. Mortality in Matrix Semigroups // The American Mathematical Monthly. 2001. Vol. 108, № 7. P. 649–653. 4. Kapovich I., Myasnikov A. G., Schupp P., Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. Vol. 264, № 2. P. 665–694. 5. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. М. : Наука, 1982. 288 с. 6. Stewart C. On divisors of Lucas and Lehmer numbers // Acta Mathematica. 2013. Vol. 211, № 2. P. 291–314. | |
Acknowledgements This research was Supported by the program of basic scientific researches SB RAS I.1.1.4, project 0314-2019-0004 | |
| Сведения об авторах Рыбалов Александр Николаевич 1.1 |
| About the authors Rybalov Alexander Nikolaevich 1.1 |
