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

В 2003 г. Каповичем, Мясниковым, Шуппом и Шпильрайном была предложена теория генерической вычислимости и сложности вычислений. В рамках этого подхода алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве «почти всех» входов. Проблема о сумме подмножеств является классической комбинаторной проблемой, изучаемой многие десятилетия. Мясников, Николаев и Ушаков в 2015 г. ввели аналог этой проблемы для произвольных групп (полугрупп). Оказалось, что для некоторых классов групп, таких, как гиперболические и нильпотентные группы, эта проблема разрешима за полиномиальное время. Для других, например групп Баумслага — Солитера и группы унимодулярных целочисленных матриц второго порядка $SL_2(\mathbb{Z})$, эта проблема NP-полна. Из работ Гуревича, Каи, Фукса, Козена и Лиу следует, что проблема о сумме подмножеств для группы $SL_2(\mathbb{Z})$ и для моноида $SL_2(\mathbb{N})$ полиномиально разрешима для почти всех входов. В работе изучается генерическая сложность проблемы о сумме подмножеств для полугрупп матриц произвольного порядка с целыми неотрицательными элементами. Эта проблема является NP-полной, а потому при условии $\text{P} \neq \text{NP}$ нет полиномиального алгоритма, решающего её для всех входов. Доказывается, что проблема является генерически разрешимой за полиномиальное время. Предлагается полиномиальный генерический алгоритм, основанный на методе динамического программирования.