В 2003 г. Каповичем, Мясниковым, Шуппом и Шпильрайном была предложена теория генерической вычислимости и сложности вычислений. В рамках этого подхода алгоритмическая проблема рассматривается не на всём множестве входов, а на некотором подмножестве «почти всех» входов. Проблема о сумме подмножеств является классической комбинаторной проблемой, изучаемой многие десятилетия. Мясников, Николаев и Ушаков в 2015 г. ввели аналог этой проблемы для произвольных групп (полугрупп). Оказалось, что для некоторых классов групп, таких, как гиперболические и нильпотентные группы, эта проблема разрешима за полиномиальное время. Для других, например групп Баумслага - Солитера и группы унимодулярных целочисленных матриц второго порядка SL2(Z), эта проблема NP-полна. Из работ Гуревича, Каи, Фукса, Козена и Лиу следует, что проблема о сумме подмножеств для группы SL2(Z) и для моноида SL2(N) полиномиально разрешима для почти всех входов. В работе изучается генерическая сложность проблемы о сумме подмножеств для полугрупп матриц произвольного порядка с целыми неотрицательными элементами. Эта проблема является NP-полной, а потому при условии P = NP нет полиномиального алгоритма, решающего её для всех входов. Доказывается, что проблема является генерически разрешимой за полиномиальное время. Предлагается полиномиальный генерический алгоритм, основанный на методе динамического программирования.
Скачать электронную версию публикации
Загружен, раз: 62
- Title О генерической сложности проблемы о сумме подмножеств для полугрупп целочисленных матриц
- Headline О генерической сложности проблемы о сумме подмножеств для полугрупп целочисленных матриц
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 50
- Date:
- DOI 10.17223/20710410/50/9
Ключевые слова
генерическая сложность, проблема о сумме подмножеств, полугруппы целочисленных матрицАвторы
Ссылки
Karp R. Reducibility among combinatorial problems // R. E. Miller and J. W. Thather (eds). Complexity of Computer Computations. IBM Research Symposia Ser. 1972. P.85-103.
Heilman M. and Merkle R. Hiding information and signatures in trapdoor knapsacks // IEEE Trans. Inform. Theory. 1978. V. 24. No. 5. P. 525-530.
Chor B. and Rivest R. A knapsack-type public key cryptosystem based on arithmetic in finite fields // IEEE Trans. Inform. Theory. 1988. V. 34. No. 5. P.901-909.
Кузюрин Н. Н. Полиномиальный в среднем алгоритм в целочисленном линейном программировании // Сибирский журнал исследования операций. 1994. Т. 1. №3. С. 38-48.
Miasnikov A., Nikolaev A., and Ushakov A. Knapsack problems in groups // Math. Comput. 2015. V. 84. P.987-1016.
Blass A. and Gurevich Yu. Matrix transformation is complete for the average case // SIAM J. Computing. 1995. V. 24. No. 1. P.24-39.
Gurevich Yu. Matrix decomposition problem is complete for the average case // Proc. 31st Ann. Symp. Foundations of Computer Science. 1990. P.802-811.
Cai J., Fuchs W., Kozen D., and Liu Z. Efficient average-case algorithms for the modular group // Proc. 35th Ann. Symp. Foundations of Computer Science. 1994. P. 143-152.
Cai J. and Liu Z. The bounded membership problem of the monoid SL2(N) // Math. Systems Theory. 1996. V. 29. P. 573-587.
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.
Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. М.: Наука, 1982. 288 с.
Zsigmondy K. Zur Theorie der Potenzreste // Monatshefte fur Math. u. Phys. 1882. V. 3. P. 265-284
О генерической сложности проблемы о сумме подмножеств для полугрупп целочисленных матриц | Прикладная дискретная математика. 2020. № 50. DOI: 10.17223/20710410/50/9
Скачать полнотекстовую версию
Загружен, раз: 191