Abelian Permutation Group Problems and Logspace Counting Classes

Amherst, Massachusetts June 21-June 24

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.2004.1313844

19th Annual IEEE Conference on Comput ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by V. Arvind Articles by T.C. Vijayaraghavan

	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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.