On the Constant-Depth Circuit Complexity of Generating Quasigroups

Abstract

We investigate the constant-depth circuit complexity of the Isomorphism Problem, Minimum Generating Set Problem (MGS), and Sub(quasi)group Membership Problem (Membership) for groups and quasigroups (=Latin squares), given as input in terms of their multiplication (Cayley) tables. Despite decades of research on these problems, lower bounds for these problems even against depth-$2$ AC circuits remain unknown. Perhaps surprisingly, Chattopadhyay, Torán, and Wagner (FSTTCS 2010; ACM Trans. Comput. Theory, 2013) showed that Quasigroup Isomorphism could be solved by AC circuits of depth $O(\log \log n)$ using $O({\log }^{2}n)$ nondeterministic bits, a class we denote ${\exists }^{{\log }^2(n)}FOLL$. We narrow this gap by improving the upper bound for many of these problems to $quasiA{C}^0$, thus decreasing the depth to constant. In particular, we show: - MGS for quasigroups is in ${\exists }^{{\log }^2(n)}{\forall }^{\log n}NTIME(\mathrm{polylog}(n))\subseteq quasiA{C}^0$. Papadimitriou and Yannakakis (J. Comput. Syst. Sci., 1996) conjectured that this problem was ${\exists }^{{\log }^2(n)}P$-complete; our results refute a version of that conjecture for completeness under $quasiA{C}^0$ reductions unconditionally, and under polylog-space reductions assuming EXP $\ne$ PSPACE. - MGS for groups is in $A{C}^1(L)$, improving on the previous upper bound of $P$ (Lucchini & Thakkar, J. Algebra, 2024). - Quasigroup Isomorphism belongs to ${\exists }^{{\log }^2(n)}A{C}^0(DTISP(\mathrm{polylog},\log )\subseteq quasiA{C}^0$, improving on the previous bound of ${\exists }^{{\log }^2(n)}L\cap {\exists }^{{\log }^2(n)}FOLL\subseteq quasiFOLL$ (Chattopadhyay, Torán, & Wagner, ibid.; Levet, Australas. J. Combin., 2023). Our results suggest that understanding the constant-depth circuit complexity may be key to resolving the complexity of problems concerning (quasi)groups in the multiplication table model.

39 pages. This is the TheoretiCS journal version