Characterization of ModL using Prime Modulus
T. Vijayaraghavan · Electronic colloquium on computational complexity · 2009
The complexity class ModL was defined by Arvind and Vijayaraghavan in [AV04] (more precisely in [Vij08, Definition 1.4.1][AV, Definition 3.1]). In this paper, under the assumption that NL = UL, we show that for every language L ∈ ModL there exists a function f ∈ #L and a function g ∈ FL such that on any input string x, we have • g(x) = 0 p for some prime p, and, • if x ∈ L then f(x) ≡ 1(mod p), • if x 6∈ L then f(x) ≡ 0(mod p). As a consequence under the assumption that NL = UL we show that