Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/978-3-540-31856-9_39 | STACS |
Keywords | Field | DocType |
finite rings r,feasible system,matrix a,linear equation,nc3 algorithm,column vector b,prime factorization,nonuniform class,problem lcon,computational complexity,linear equations | Finite ring,Discrete mathematics,Combinatorics,System of linear equations,Upper and lower bounds,Matrix (mathematics),Prime factor,Integer matrix,Prime power,Mathematics,Computational complexity theory | Conference |
Volume | ISSN | ISBN |
3404 | 0302-9743 | 3-540-24998-2 |
Citations | PageRank | References |
3 | 0.44 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| T. C. Vijayaraghavan | 2 | 19 | 3.54 |