Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-099 | 20th June 2010 11:20

A Note on Closure Properties of ModL

RSS-Feed




TR10-099
Authors: T.C. Vijayaraghavan
Publication: 20th June 2010 15:55
Downloads: 4396
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\subseteqL-uniform TC1.



ISSN 1433-8092 | Imprint