.
In this paper we classify the complexity of several problems based on Abelian permutation groups and linear congruences using logspace counting classes. The problems we consider were defined by McKenzie & Cook (1987).
Central to our study is the problem LCON: given as input (A, b, q), where $$A \in {\mathbb{Z}}^{m \times n}$$ and b $$\in {\mathbb{Z}}^m$$ , the problem is to determine if Ax = b is a feasible system of linear equations over $${\mathbb{Z}}_q$$ . We assume that q is given by its prime factorization $$q = p^{e_1}_{1} p^{e_2}_{2} \cdot \cdot \cdot p^{e_k}_{k}$$ , such that each $$p^{e_i}_i$$ is tiny (i.e. given in unary). We give a randomized NC2 algorithm for LCON. More precisely, LCON is in the nonuniform class LGapL/poly. As LCON is hard for LGapL we get a fairly tight characterization of LCON in terms of logspace counting classes. We derive the same upper bound for computing a basis for the nullspace of a linear map from $${\mathbb{Z}}^n_q$$ to $${\mathbb{Z}}^m_q$$ . A number of Abelian permutation group problems studied in McKenzie & Cook (1987) turn out to be logspace Turing equivalent to these linear-algebraic problems. Consequently, the upper and lower bounds also carry over to these problems.