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

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

2012-02-17

arxiv.org/abs/1202.3949v2

Computer Science

Computational Complexity

16 pages; minor corrections, added further remarks. Comments welcome

Scientific paper

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 of these problems are considered modulo an arbitrary constant k>1. These problems are known to be complete for the logspace modular counting classes coMod-k-L in special case that k is prime [Buntrock et al, Theor.Comp.Sys. 25 (p.223), 1992]. By considering relaxed modular variants of standard logspace function classes, related to #L and functions computable by UL machines but only characterizing the number of accepting paths mod k, we show that these problems of linear algebra are also complete for coMod-k-L for any constant k>1.

Affiliated with

Also associated with

No associations

Rating

On the complexity of solving linear congruences and computing nullspaces modulo a constant does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the complexity of solving linear congruences and computing nullspaces modulo a constant, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of solving linear congruences and computing nullspaces modulo a constant will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-36311