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

Abstract

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$.

• The article: PDF (275 KB)
• Source material: ZIP (93 KB)
• BibTeX entry for this article (282 bytes)

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

© 2013 Niel de Beaudrap
Licensed under a Creative Commons Attribution License

Article 9

Article 11

Volume 2013

Published articles