Generic NP-completeness of the problems of solving of systems of equations over finite groups, semigroups and fields
И. Ф. Горкун, Alexander Rybalov · Herald of Omsk University · 2024
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.