Notes on extended equation solvability and identity checking for groups

Abstract

Every finite non-nilpotent group can be extended by a term operation such that solving equations in the resulting algebra is NP-complete and checking identities is co-NP-complete. This result was firstly proven by Horvath and Szabo; the term constructed in their proof depends on the underlying group.

In this paper we provide a uniform term extension that induces hard problems. In doing so we also characterize a big class of solvable, non-nilpotent groups for which extending by the commutator operation suffices.

Keywords

• equation solvability
• identity checking
• solvable group