Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-099 | 20th June 2010 11:20

A Note on Closure Properties of ModL


Authors: T.C. Vijayaraghavan
Publication: 20th June 2010 15:55
Downloads: 3947


Recently in [Vij09, Corollary 3.7] the complexity class ModL has been shown to be closed under complement assuming NL = UL. In this note we continue to show many other closure properties of ModL which include the following.

1. ModL is closed under $\leq ^L_m$ reduction, $\vee$(join) and $\leq ^{UL}_m$ reduction,
m reduction

2. ModL is closed under $\leq ^L_{1-tt}$ and $\leq ^{UL}_{1-tt}$ reduction assuming NL =

3. ModL$^{UL}$=ModL assuming UL=coUL,

4. $UL^{ModL}_{1-tt}$=$ModL^{UL}$=ModL assuming NL = UL,

5. if $l\in Z^{+}$ such that $l\geq 2$ and ModL is closed under $\leq ^L_{l-dtt}$ reduction then $Mod_kL\subseteq ModL$ for all $k\in Z^{+}$ such that $k\geq 6$ is a composite
number and $k$ has at least $2$ and at most $l$ distinct prime divisors, and

6. if ModL is closed under $\leq ^L_{dtt}$ reduction then $coC=L\subseteq ModL$.
Also using [Vij09, Corollary 3.7] we show that if NL = UL and ModL is closed under $\leq ^L_{
l-dtt} and $\leq ^L_{dtt}$ reduction then ModL is also closed under $\leq ^L_{1-ctt}$ and $\leq ^L_{ctt}$ reduction respectively.

We also show a proof of the well known result that the determinant of a matrix with entries in Z is computable in L-uniform TC1 from which it follows that ModL$\subseteq$L-uniform TC1.

ISSN 1433-8092 | Imprint