Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-082 | 20th September 2009 16:32

Characterization of ModL using Prime Modulus.


Authors: T.C. Vijayaraghavan
Publication: 24th September 2009 15:34
Downloads: 2780


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 $L\in ModL$ there exists a function $f\in \sharpL$ and a function $g\in FL$ such that on any input string $x$, we have
1. $g(x)=0^p$ for some prime $p$, and,
2. if $x\in L$ then $f(x)\equiv 1(\mod p)$,
3. if $x\not \in L$ then $f(x)\equiv 0(\mod p)$.

As a consequence under the assumption that NL=UL we show that
1. $\ModL$ is the logspace analogue of the complexity class $ModP$ defined by K\"obler and Toda in \cite[Definition 3.1,KT96], and that
2. $\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\in \sharpL$ and $g\in FL$ such that $g(x)$ is a positive integer $k$ in unary that depends on the input $x$ then the function
${{f(x)}\choose{k}} \in \sharpL$.

ISSN 1433-8092 | Imprint