首页    期刊浏览 2025年01月19日 星期日
登录注册

文章基本信息

  • 标题:Characterization of ModL using Prime Modulus.
  • 本地全文:下载
  • 作者:T.C. Vijayaraghavan
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2009
  • 卷号:2009
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The complexity class ModL was defined by Arvind and Vijayaraghavan in [AV04] (more precisely in Definition 1.4.1, Vij08],[Definition 3.1, AV]). In this paper, under the assumption that NL =UL, we show that for every language LModL there exists a function f\sharpL and a function gFL such that on any input string x, we have1. g(x)=0p for some prime p, and,2. if xL then f(x)1(\modp),3. if xL then f(x)0(\modp).

    As a consequence under the assumption that NL=UL we show that1. \ModL is the logspace analogue of the complexity class ModP defined by K\"obler and Toda in \cite[Definition 3.1,KT96], and that2. \ModL is closed under complement.

    We prove the characterization of ModL stated above by showing the following property of \sharpL. Assuming NL =UL, if f\sharpL and gFL such that g(x) is a positive integer k in unary that depends on the input x then the functionkf(x)\sharpL .

  • 关键词:Logspace counting classes; Modulo based computation
国家哲学社会科学文献中心版权所有