Chicago Journal of Theoretical Computer Science

Volume 2013

Article 10

Published by the Department of Computer Science, The University of Chicago.

On the complexity of solving linear congruences and computing nullspaces modulo a constant

Niel de Beaudrap
Department of Applied Mathematics and Theoretical Physics
University of Cambridge
Cambridge, UK
niel DOT debeaudrap AT gmail DOT com

July 27, 2013


We consider the problems of determining the feasibility of a linear congruence, producing a solution to a linear congruence, and finding a spanning set for the nullspace of an integer matrix, where each problem is considered modulo an arbitrary constant $k \geqslant 2$. These problems are known to be complete for the logspace modular counting classes $\mathrm{Mod_k L = coMod_k L}$ in the special case when $k$ is prime (Buntrock et al 1992). By considering variants of standard logspace function classes -- related to $\mathrm{\#L}$ and functions computable by $\mathrm{UL}$ machines, but which only characterize the number of accepting paths modulo $k$ -- we show that these problems of linear algebra are also complete for $\mathrm{coMod_k L}$ for any constant $k \geqslant 2$.

Our results are obtained by defining a class of functions $\mathrm{FUL_k}$ which are low for $\mathrm{Mod_k L}$ and $\mathrm{coMod_k L}$ for $k \geqslant 2$, using ideas similar to those used in the case of k prime in (Buntrock et al 1992) to show closure of $\mathrm{Mod_k L}$ under $\mathrm{NC^1}$ reductions (including $\mathrm{Mod_k L}$ oracle reductions). In addition to the results above, we briefly consider the relationship of the class $\mathrm{FUL_k}$ for arbitrary moduli $k$ to the class $\mathrm{F \cdot coMod_k L}$ of functions whose output symbols are verifiable by $\mathrm{coMod_k L}$ algorithms; and consider what consequences such a comparison may have for oracle closure results of the form $\mathrm{Mod_k L^{Mod_k L} = Mod_k L}$ for composite $k$.

Submitted September 13, 2012, revised July 11, 2013; published July 27, 2013.

DOI: 10.4086/cjtcs.2013.010

[] Article 9 [] Article 11
[back] Volume 2013 [back] Published articles
[CJCTS home]