ECCC-Report TR10-099https://eccc.weizmann.ac.il/report/2010/099Comments and Revisions published for TR10-099en-usSun, 20 Jun 2010 15:55:33 +0300
Paper TR10-099
| A Note on Closure Properties of ModL |
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2010/099Recently 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.
Sun, 20 Jun 2010 15:55:33 +0300https://eccc.weizmann.ac.il/report/2010/099