| Генерическая NP-полнота проблем разрешимости систем уравнений над конечными группами, полугруппами и полями | |
| Горкун И.Ф.1, Рыбалов А. Н.2 | |
| Дата поступления 2024.10.09 | Аннотация. В данной работе доказывается, что проблемы разрешимости систем уравнений над конечными полями, неабелевыми конечными группами и некоммутативными конечными моноидами являются полными относительно генерической полиномиальной сводимости в генерическом аналоге класса NP. |
| Ключевые слова генерическая сложность, NP-полнота, конечные алгебраические сиситемы | |
Библиография \bibitem{GR} Goldmann M., Russell A. The Complexity of Solving Equations over Finite Groups // Information and Computation. 2002. Vol.~178. P.~253--262. \bibitem{KTT} Klima O., Tesson P., Therien D. Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups // Theory of Computing Systems. 2007. Vol.~40. P.~263--297. \bibitem{Ryb} Рыбалов А. О генерической NP-полноте проблемы выполнимости булевых формул // Прикладная дискретная математика. 2017. №~36. C.~106--112. \bibitem{KMSS} Kapovich I., Myasnikov A., Schupp P., Shpilrain V. Generic-case complexity and decision problems in group theory // Journal of Algebra. 2003. Vol.~264. P.~665--694. \bibitem{RS} Rybalov A., Shevlyakov A. Generic complexity of solving of equations in finite groups, semigroups and fields // Journal of Physics: Conference series. 2021. Vol.~1901. P.~1--8. | |
Сведения о финансировании и благодарности Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003. | |
| Generic NP-completeness of the problems of solving of systems of equations over finite groups, semigroups and fields | |
| 1, Rybalov A. N.2 | |
| Received 2024.10.09 | Abstract. In this paper we prove that problems of solvability of systems of equations over finite fields, non-Abelian finite groups and non-commutative finite monoids are complete with respect to generic polynomial reducibility in generic analogue of the NP class. |
| Keywords generic complexity, NP-completeness, finite algebraic structures | |
References \bibitem{GR} Goldmann M., Russell A. The Complexity of Solving Equations over Finite Groups // Information and Computation. 2002. Vol.~178. P.~253--262. \bibitem{KTT} Klima O., Tesson P., Therien D. Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups // Theory of Computing Systems. 2007. Vol.~40. P.~263--297. \bibitem{Ryb} Рыбалов А. О генерической NP-полноте проблемы выполнимости булевых формул // Прикладная дискретная математика. 2017. №~36. C.~106--112. \bibitem{KMSS} Kapovich I., Myasnikov A., Schupp P., Shpilrain V. Generic-case complexity and decision problems in group theory // Journal of Algebra. 2003. Vol.~264. P.~665--694. \bibitem{RS} Rybalov A., Shevlyakov A. Generic complexity of solving of equations in finite groups, semigroups and fields // Journal of Physics: Conference series. 2021. Vol.~1901. P.~1--8. | |
Acknowledgements Работа выполнена в рамках государственного задания ИМ СО РАН, проект FWNF-2022-0003. | |
| Сведения об авторах Горкун И.Ф. Рыбалов А. Н. |
| About the authors Rybalov A. N. |
