Дата публикации: 2020

Дата публикации в реестре: 2021-01-19T20:04:00Z

Аннотация:

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

Тип: статьи в журналах

Источник: Прикладная дискретная математика. 2020. № 50. С. 118-126