The complexity of the equation solvability problem over nilpotent groups

Let G be a finite, nilpotent group. The computational complexity of the equation solvability problem over G is known to be in P. The complexity is understood in the length of the equation over G. So far the fastest algorithm to decide whether or not an equation of length n has a solution over G was running in O(n|G||G|⋯|G||G|) time. Here the height of the tower is the nilpotency class of G. We prove that one can decide in O(n12|G|2log⁡|G|) time whether an equation of length n has a solution over G. The key ingredient of the proof is to represent group expressions using the polycyclic presentation of p-groups.