ECCC-Report TR09-082https://eccc.weizmann.ac.il/report/2009/082Comments and Revisions published for TR09-082en-usThu, 24 Sep 2009 15:34:17 +0300
Paper TR09-082
| Characterization of ModL using Prime Modulus. |
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2009/082The 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$.Thu, 24 Sep 2009 15:34:17 +0300https://eccc.weizmann.ac.il/report/2009/082