首页    期刊浏览 2024年11月29日 星期五
登录注册

文章基本信息

  • 标题:On the complexity of solving linear congruences and computing nullspaces modulo a constant
  • 本地全文:下载
  • 作者:Niel de Beaudrap
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:2013
  • 卷号:2013
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    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$

国家哲学社会科学文献中心版权所有