Проблема вхождения в конечно порождённую подгруппу (подполугруппу) для групп (полугрупп) является классической алгоритмической проблемой в алгебре, активно изучаемой многие десятилетия. Уже для достаточно простых групп и полугрупп эта проблема становится неразрешимой. Например, К. А. Михайлова в 1966 г. доказала неразрешимость проблемы вхождения в конечно порождённые подгруппы и, следовательно, подполугруппы для прямого произведения F2×F2 двух свободных групп ранга 2. Так как по известной теореме Санова группа F2 имеет точное представление целочисленными матрицами порядка 2, группа F2×F2 является подгруппой группы GL4(ℤ) целочисленных матриц порядка 4. Отсюда легко следует неразрешимость рассматриваемой проблемы для группы GLk(ℤ) при k ≥ 4. Неразрешимость проблемы вхождения в подполугруппы полугрупп целочисленных матриц порядка ≥ 3 следует из результата М. Патерсона 1970 г. В данной работе предлагается сильно генерический алгоритм, решающий проблему вхождения в подполугруппы полугрупп целочисленных матриц произвольного порядка для подмножества входов, последовательность относительных плотностей которого при увеличении размера экспоненциально быстро сходится к 1.
Скачать электронную версию публикации
Загружен, раз: 57
- Title О генерической сложности проблемы вхождения для полугрупп целочисленных матриц
- Headline О генерической сложности проблемы вхождения для полугрупп целочисленных матриц
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 55
- Date:
- DOI 10.17223/20710410/55/7
Ключевые слова
генерическая сложность, проблема вхождения, полугруппа целочисленных матрицАвторы
Ссылки
Михайлова К. А. Проблема вхождения для прямых произведений групп // Математический сборник. 1966. Т. 112. №2. С.241-251.
Paterson M. S. Unsolvability in 3 x 3 matrices // Studies Appl. Math. 1970. V. 49. No. 1. P. 105-107.
Halava V. and Harju T. Mortality in matrix semigroups // Amer. Math. Monthly. 2001. V. 108. No. 7. P. 649-653.
Kapovich I., Miasnikov A, Schupp P., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks //j. Algebra. 2003. V. 264. No. 2. P. 665-694.
Babai L., Erdos P, and Selkow S. Random graph isomorphism // SIAM J.Computing. 1980. V. 9. No. 3. P. 628-635.
Гимади Э. X., Глебов Н. И., Перепелица В. А. Алгоритмы с оценками для задач дискретной оптимизации // Проблемы кибернетики. 1975. Т. 31. С. 35-42.
Селиверстов А.В. Двоичные решения для больших систем линейных уравнений // Прикладная дискретная математика. 2021. №52. C.5-15.
Gurevich Y. Average case completeness //j.Computer System Sci. 1991. V.42. P.346-398.
Levin L. Average case complete problems // SIAM J.Computing. 1987. V. 15. P. 285-286.
Рыбалов А. Генерический алгоритм для проблемы вхождения в полугруппах целочисленных матриц // Вестник Омского университета. 2020. Т. 25. №3. С. 8-12.
Hirschfeldt D. Some questions in computable mathematics // Computability and Complexity. 2017. P.22-55. О генерической сложности проблемы вхождения для полугрупп целочисленных матриц 101
Meyer A. An open problem on creative sets // Recursive Function Theory Newsletter. 1973. V. 4. P. 15-16.
Jockusch C. and Schupp P. Generic computability, Turing degrees, and asymptotic density //j. London Math. Soc. 2012. V. 85. No. 2. P.472-490.
Schwartz J. Fast probabilistic algorithms for verification of polynomial identities //j. ACM. 1980. V. 27. No. 4. P.701-717.
Zippel R. Probabilistic algorithms for sparse polynomials // Symbolic Algebraic Computation. 1979. V. 72. P.216-226.
DeMillo R. and Lipton R. A probabilistic remark on algebraic program testing // Inform. Processing Lett. 1978. V. 7. P. 193-195.
О генерической сложности проблемы вхождения для полугрупп целочисленных матриц | Прикладная дискретная математика. 2022. № 55. DOI: 10.17223/20710410/55/7
Скачать полнотекстовую версию
Загружен, раз: 155