On the complexity of solving equations over the symmetric group $S_4$

Abstract

The complexity of solving equations over finite groups has been an active area of research over the last two decades, starting with Goldmann and Russell, \emph{The complexity of solving equations over finite groups} from 1999. One important case of a group with unknown complexity is the symmetric group $S_4.$ In 2023, Idziak, Kawałek, and Krzaczkowski published $\exp (\Omega ({\log }^{2}n))$ lower bounds for the satisfiability and equivalence problems over $S_4$ under the Exponential Time Hypothesis. In the present note, we prove that the satisfiability problem $\textsc{PolSat}(S_4)$ can be reduced to the equivalence problem $\textsc{PolEqv}(S_4)$ and thus, the two problems have the same complexity. We provide several equivalent formulations of the problem. In particular, we prove that $\textsc{PolEqv}(S_4)$ is equivalent to the circuit equivalence problem for $\mathrm{CC}[2,3,2]$-circuits, which were introduced by Idziak, Kawełek and Krzaczkowski. Under their strong exponential size hypothesis, such circuits cannot compute ${\mathrm{AND}}_n$ in size $\exp (o(\sqrt{n})).$ Our results provide an upper bound on the complexity of $\textsc{PolEqv}(S_4)$ that is based on the minimal size of ${\mathrm{AND}}_n$ over $\mathrm{CC}[2,3,2]$-circuits.