...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational complexity >CLASSIFYING PROBLEMS ON LINEAR CONGRUENCES AND ABELIAN PERMUTATION GROUPS USING LOGSPACE COUNTING CLASSES
【24h】

CLASSIFYING PROBLEMS ON LINEAR CONGRUENCES AND ABELIAN PERMUTATION GROUPS USING LOGSPACE COUNTING CLASSES

机译：使用对数计数类的线性同余和Abel置换组的分类问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this paper we classify the complexity of several problems based on Abelian permutation groups and linear congruences using logspace counting classes. The problems we consider were defined by McKenzie & Cook (1987).rnCentral to our study is the problem LCON: given as input (A,b,q), where A ∈ Z~(m×n) and b ∈ Z~m, the problem is to determine if Ax = b is a feasible system of linear equations over Z_q. We assume that q is given by its prime factorization q = p_1~(e_1)p_2~(e_2) … p_k~(e_k), such that each p_i~(e_i) is tiny (i.e. given in unary). We give a randomized NC2 algorithm for LCON. More precisely, LCON is in the nonuniform class L~(GapL)/poly. As LCON is hard for L~(GapL) we get a fairly tight characterization of LCON in terms of logspace counting classes. We derive the same upper bound for computing a basis for the nullspace of a linear map from Z_q~nto Z_q~m.A number of Abelian permutation group problems studied in McKenzie & Cook (1987) turn out to be logspace Turing equivalent to these linear-algebraic problems. Consequently, the upper and lower bounds also carry over to these problems.
机译：在本文中，我们使用对数空间计数类基于Abelian置换组和线性同余性对几个问题的复杂性进行了分类。我们考虑的问题由McKenzie＆Cook（1987）定义。rn研究的核心是问题LCON：作为输入（A，b，q）给出，其中A∈Z〜（m×n）和b∈Z〜m ，问题是要确定Ax = b是否是Z_q上的线性方程组的可行系统。我们假设q由其素数分解q = p_1〜（e_1）p_2〜（e_2）…p_k〜（e_k）给出，使得每个p_i〜（e_i）很小（即，以一元形式给出）。我们给出了LCON的随机NC2算法。更准确地说，LCON是非均匀类L〜（GapL）/ poly。由于LCON很难满足L〜（GapL）的要求，因此我们可以从对数空间计数类的角度对LCON进行严格的描述。我们从Mc_Kenzie＆Cook（1987）研究的Abelian置换群问题的Z_q〜n至Z_q〜mA数推导计算线性图的零空间的基础的相同上限，证明是对数空间Turing等效于这些线性代数问题。因此，上限和下限同样会影响这些问题。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号