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.