Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR10-099 | 20th June 2010 11:20

#### A Note on Closure Properties of ModL

TR10-099
Authors: T.C. Vijayaraghavan
Publication: 20th June 2010 15:55
Keywords:

Abstract:

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 =
UL,

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