Abstract
In this paper we first examine the computational complexity of the problem LCON defined as follows: given a matrix A and a column vector b over ℤ, determine if Ax = b is a feasible system of linear equations over ℤ q . Here q is also given as part of the input by its prime factorization \(q = p^{e_1}_{1}p^{e_2}_{2}p^{e_k}_{k}\), such that each \(p^{e_i}_{i}\) is tiny (i.e. given in unary). In [MC87] an NC3 algorithm is given for this problem. We show that in fact the problem can be solved in randomized NC2. More precisely, we show that LCON is in the nonuniform class LGapL/poly. Combined with the hardness of LCON for LGapL, we have a fairly tight characterization of the complexity of LCON in terms of logspace counting classes. We prove the same upper bound results for the problem of testing feasibility of Ax = b over finite rings R with unity, where R is given as part of the input as a table.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arvind, V., Vijayaraghavan, T.C.: Abelian Permutation Group Problems and Logspace Counting Classes. In: IEEE Annual Conference on Computational Complexity (CCC 2004), pp. 204–214 (2004)
Allender, E., Beals, R., Ogihara, M.: The complexity of matrix rank and feasible systems of linear equations. Computational Complexity 8, 99–126 (1999)
Allender, E., Reinhardt, K., Zhou, S.: Isolation, matching, and counting: Uniform and nonuniform upper bounds. Journal of Computer and System Sciences 59, 164–181 (1999)
Buntrock, G., Damm, C., Hertrampf, U., Meinel, C.: Structure and Importance of Logspace-MOD Classes. Mathematical Systems Theory 25(3), 223–237 (1992)
Dickson, L.E.: History of the theory of numbers. Diophantine analysis, vol. II. Chelsea Publishing Company, New York (1992)
Giesbrecht, M.: Fast computations of the Smith Normal Form of an integer matrix. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 110–118 (1995)
Giesbrecht, M.: Efficient parallel solution of sparse systems of linear diophantine equations. In: Proceedings of the second international symposium on Parallel Symbolic Computation, pp. 1–10 (1997)
Klivans, A., van Melkebeek, D.: Graph Isomorphism has subexponential size provers unless the polynomial time hierarchy collapses. SIAM Journal of Computing 31(5), 1501–1526 (2002)
McKenzie, P., Cook, S.: The parallel complexity of abelian permutation group problems. Siam Journal on Computing 16, 880–909 (1987)
Schrijver, A.: Theory of Linear and Integer Programming. John Wiley, Chichester (1998)
Shoda, K.: Über die Automorphismen einer endlichen Abelschen Gruppe. Mathematische Annalen 100, 674–686 (1928); Source: The Göttingen State and University Library, http://www.sub.uni-goettingen.de
Toda, S.: Counting problems computationally equivalent to computing the determinant. Technical Report CSIM 91-07, Department of Computer Science, University of Electro-Communications, Tokyo, Japan (May 1991)
Vinay, V.: Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In: Structure in Complexity Theory Conference, pp. 270–284 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arvind, V., Vijayaraghavan, T.C. (2005). The Complexity of Solving Linear Equations over a Finite Ring. In: Diekert, V., Durand, B. (eds) STACS 2005. STACS 2005. Lecture Notes in Computer Science, vol 3404. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31856-9_39
Download citation
DOI: https://doi.org/10.1007/978-3-540-31856-9_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24998-6
Online ISBN: 978-3-540-31856-9
eBook Packages: Computer ScienceComputer Science (R0)
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.