Equation satisfiability in solvable groups (Q6614610)

Let \(G\) be a group and \(\mathbf{t}, \mathbf{s}\) be polynomials over \(G\), that is words in a free group of countable rank. The problem \textsc{PolSat}\((G)\) takes as input an equation of the form \(\mathbf{t}(x_{1}, \ldots, x_{n}) = \mathbf{s}(x_{1},\ldots , x_{n})\) and asks whether this equation has a solution in \(G\). Likewise \textsc{PolEqv}\((G)\) is the problem of deciding whether two polynomials \(\mathbf{t}\) and \(\mathbf{s}\) are equal for all evaluations of the variables \(x_{1}, \ldots, x_{n}\) in \(G\).\N\NWhile for infinite groups \(G\) the problems \textsc{PolSat}\((G)\) and \textsc{PolEqv}\((G)\) may be undecidable, they are solvable in exponential time in finite groups. In fact, in finite groups, \textsc{PolSat} is in \textsf{NP}, whereas \textsc{PolEqv} is in \textsf{coNP}. On the other hand it is easy to see that both these problems can be solved in a linear time for all finite abelian groups. Also in nilpotent groups both \textsc{PolSat} and \textsc{PolEqv} can be solved in polynomial time, as \textit{M. Goldmann} and \textit{A. Russell} have shown in [Inf. Comput. 178, No. 1, 253--262 (2002; Zbl 1012.68087)].\N\NUp to recently, the smallest solvable non-nilpotent group with unknown complexity was the symmetric group \(S_{4}\). One reason that prevented existing techniques for polynomial time algorithms to work for \(S_{4}\) is that \(S_{4}\) does not have a nilpotent normal subgroup with a nilpotent quotient. The first three authors have proved [in: Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8--11, 2020. New York, NY: Association for Computing Machinery (ACM). 578--590 (2020; Zbl 07299497)] that neither \textsc{PolSat}\((S_{4})\) nor \textsc{PolEqv}\((S_{4})\) is in \textsf{P} as long as the ETH (existential time hypothesis) holds.\N\NThe main result in the paper under review is Theorem 1: If \(G\) is a finite solvable group of Fitting length \(d\geq 3\), then both \textsc{PolSat}\((G)\) and \textsc{PolEqv}\((G)\) require (for polynomials of length \(\ell\)) at least \(2^{\Omega(\log^{d-1} \ell)}\) steps unless ETH fails.\N\NThe authors point out that allowing to use definable polynomials as additional basic operations to build the input terms \(\mathbf{t}\), \(\mathbf{s}\) it is possible substantially shorten the size of the input. For example, with the commutator \([x,y]=x^{-1}y^{-1}xy\) the expression \([x, y_{1}, y_{2}, \ldots, y_{n}]\) has linear size, while when presented in the pure group language it has exponential size. In this new setting, \textsc{PolSat} and \textsc{PolEqv} have been shown to be \textsf{NP}-complete (or \textsf{coNP}-complete, respectively) for all non-nilpotent groups (see [\textit{G. Horváth} and \textit{C. Szabó}, Discrete Math. Theor. Comput. Sci. 13, No. 4, 23--32 (2011; Zbl 1286.68194); \textit{M. Kompatscher}, Acta Math. Hung. 159, No. 1, 246--256 (2019; Zbl 1438.20035)]. Actually the proof of Theorem 1 shows this as well.