Name
Abstract | ||
|---|---|---|
The goal of this paper is to classify abelian permutationgroup problems using logspace counting classes.Building on McKenzie and Cookýs [MC87] classification of permutation group problems into four NC^1 Turing-equivalent sets, we show that all these problemsare essentially captured by the generalized logspace modclassModL, where ModL is the logspace analogue ofModP (defined by Köbler and Toda [KT96]).More precisely, our results are as follows:1. For abelian permutation groups, the problems ofmembership testing, isomorphism testing and computingthe order of a group are all in ZPL^ModL, andare all hard for ModL under logspace Turing reductions.2. The problems of computing the intersection ofabelian permutation groups, and computing agenerator-relator presentation for a given abelianpermutation group are in FL^ModL /poly. Furthermore,the search version of membership testing isalso in FL^ModL /poly. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1109/CCC.2004.1 | IEEE Conference on Computational Complexity |
Keywords | Field | DocType |
Turing machines,computational complexity,group theory,Abelian permutation group,ModL,ModP,NC Turing-equivalent sets,isomorphism testing,logspace Turing reductions,logspace analogue,logspace counting classes,logspace mod-class,membership testing | L,Discrete mathematics,Abelian group,Combinatorics,Group theory,Cyclic permutation,Permutation group,Isomorphism,Turing machine,Mathematics,Order (group theory) | Conference |
ISSN | ISBN | Citations |
1093-0159 | 0-7695-2120-7 | 5 |
PageRank | References | Authors |
0.57 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| V. Arvind | 1 | 122 | 12.03 |
| T. C. Vijayaraghavan | 2 | 19 | 3.54 |