TR09-082 Authors: T.C. Vijayaraghavan

Publication: 24th September 2009 15:34

Downloads: 2780

Keywords:

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$.