Publication at Faculty of Mathematics and Physics |
2018
Abstract
In 2011, Horvath gave a new proof that the equation solvability problem over finite nilpotent groups and rings is in P. In the same paper, he asked whether his proof can be lifted to nilpotent algebras in general.
We show that this is in fact possible for supernilpotent algebras with a Mal'cev term. However, we also describe a class of nilpotent, but not supernilpotent algebras with Mal'cev term that have co-NP-complete identity checking problems and NP-complete equation solvability problems.
This proves that the answer to Horvath's question is negative in general (assuming P not equal NP).