Abelian permutation group problems and logspace counting classes
V. Arvind, T. Vijayaraghavan · Conference on Computational Complexity · 2004
The goal of this paper is to classify abelian permutation group problems using logspace counting classes. Building on McKenzie and Cook's [MC87] classification of permutation group problems into four NC Turing-equivalent sets, we show that all these problems are essentially captured by the generalized logspace mod-class ModL, where ModL is the logspace analogue of ModP (defined by Kobler and Toda (KT96)). More precisely, our results are as follows: 1. For abelian permutation groups, the problems of membership testing, isomorphism testing and computing the order of a group are all in ZPL/sup ModL/, and are all hard for ModL under logspace Turing reductions. 2. The problems of computing the intersection of abelian permutation groups, and computing a generator-relator presentation for a given abelian permutation group are in FL/sup ModL//poly. Furthermore, the search version of membership testing is also in FL/sup ModL//poly.