loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
19th Annual IEEE Conference on Computational Complexity (CCC'04)
Abelian Permutation Group Problems and Logspace Counting Classes
Amherst, Massachusetts
June 21-June 24
ISBN: 0-7695-2120-7
ASCII Text
x 
 
V. Arvind, T.C. Vijayaraghavan, "Abelian Permutation Group Problems and Logspace Counting Classes," Computational Complexity, Annual IEEE Conference on, pp. 204-214, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2004.1313844,
author = {V. Arvind and T.C. Vijayaraghavan},
title = {Abelian Permutation Group Problems and Logspace Counting Classes},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2004},
issn = {1093-0159},
pages = {204-214},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313844},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Abelian Permutation Group Problems and Logspace Counting Classes
SN - 1093-0159
SP204
EP214
A1 - V. Arvind,
A1 - T.C. Vijayaraghavan,
PY - 2004
KW - null
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
V. Arvind, Institute ofMathematical Sciences
T.C. Vijayaraghavan, Institute ofMathematical Sciences

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^1 Turing-equivalent sets, we show that all these problems are essentially captured by the generalized logspace modclass ModL, where ModL is the logspace analogue of ModP (defined by Köbler 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^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^ModL /poly. Furthermore, the search version of membership testing is also in FL^ModL /poly.

    • Citation:
    V. Arvind, T.C. Vijayaraghavan, "Abelian Permutation Group Problems and Logspace Counting Classes," ccc, pp.204-214, 19th Annual IEEE Conference on Computational Complexity (CCC'04), 2004
    Usage of this product signifies your acceptance of the Terms of Use.