О генерической сложности проблемы вхождения для полугрупп целочисленных матриц

Проблема вхождения в конечно порождённую подгруппу (подполугруппу) для групп (полугрупп) является классической алгоритмической проблемой в алгебре, активно изучаемой многие десятилетия. Уже для достаточно простых групп и полугрупп эта проблема становится неразрешимой. Например, К. А. Михайлова в 1966 г. доказала неразрешимость проблемы вхождения в конечно порождённые подгруппы и, следовательно, подполугруппы для прямого произведения $F_2 \times F_2$ двух свободных групп ранга $2$. Так как по известной теореме Санова группа $F_2$ имеет точное представление целочисленными матрицами порядка $2$, группа $F_2 \times F_2$ является подгруппой группы $\text{GL}_4 (\mathbb{Z})$ целочисленных матриц порядка $4$. Отсюда легко следует неразрешимость рассматриваемой проблемы для группы $\text{GL}_{k} (\mathbb{Z})$ при $k \geq 4$. Неразрешимость проблемы вхождения в подполугруппы полугрупп целочисленных матриц порядка $\geq 3$ следует из результата М. Патерсона 1970 г. В данной работе предлагается сильно генерический алгоритм, решающий проблему вхождения в подполугруппы полугрупп целочисленных матриц произвольного порядка для подмножества входов, последовательность относительных плотностей которого при увеличении размера экспоненциально быстро сходится к $1$.