Structure and Importance of Logspace-MOD-Classes
Structure and Importance of Logspace-MOD-Classes
复制标题
Logspace-MOD 类的结构和重要性
DOI：
10.1007/bfb0020812
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
C. Meinel
中科院分区：
文献类型：
--
作者：
G. Buntrock;C. Damm;U. Hertrampf;C. Meinel
我们改进了Beigel，Gill，Hertrampf [BGH 90]研究多项式时间计数类的技术，以便使其适用于对数空间的情况。我们定义的复杂性类MODkL，并证明其意义，证明了所有的标准问题的线性代数在有限环Z/kZ是完整的这些类。然后，我们定义了新的复杂性类LogFew和LogFewNL，并将它们确定为Few和LogFew和FewP的适当的对数空间版本。我们表明，LogFew和LogFewNL包含在MODZkL和LogFew包含在MODkL的所有k。还给出了L #L在整数行列式计算方面的一个上界，由此我们得出结论，所有的对数空间计数类都包含在NC 2中。
We refine the techniques of Beigel, Gill, Hertrampf [BGH90] who investigated polynomial time counting classes, in order to make them applicable to the case of logarithmic space. We define the complexity classes MODkL and demonstrate their significance by proving that all standard problems of linear algebra over the finite rings Z/kZ are complete for these classes. We then define new complexity classes LogFew and LogFewNL and identify them as adequate logspace versions of Few and LogFew and FewP. We show that LogFew and LogFewNL is contained in MODZkL and that LogFew is contained in MODkL for all k. Also an upper bound for L #L in terms of computation of integer determinants is given from which we conclude that all logspace counting classes are contained in NC2.