#

### 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*
#### 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.

Article 9
Article 11

Volume 2013
Published articles