Abstract:
Constraint satisfaction on finite groups, with subgroups and their cosets described by generators, has a polynomial time algorithm. For any given group, a single additional constraint type that is not a coset of a near subgroup makes the problem NP-complete. We consider constraint satisfaction on groups with subgroups, near subgroups, and their cosets. We give two polynomial time algorithms for the case of solvable groups. We then give a polynomial time algorithm for general groups with subgroups, near subgroups, and their cosets. Bulatov has shown that Mal'tsev constraints have a polynomial time algorithm; we finally show that subgroups, near subgroups, and their cosets are Mal'tsev constraints. Our results generalize the results of Bulatov on Mal'tsev in the special case of near subgroups and some cases of twisted subgroups by only requiring the subgroups and their cosets to be given by generators describing possibly a constraint of exponential size, and allowing different variables to have different domains of varying size, with corresponding group operations.