DocumentCode
2185051
Title
The complexity of isomorphism testing
Author
Garzon, Max ; Zalcstein, Yechezkel
fYear
1986
fDate
27-29 Oct. 1986
Firstpage
313
Lastpage
321
Abstract
A polynomial time isomorphism test for a class of groups, properly containing the class of abelian groups, is presented. Isomorphism testing of group presentations for (a subclass of) the same class of groups is shown to be (graph) isomorphism complete. These seem to be the first known isomorphism complete problems in group theory. Subexponential tests are presented as well for rings and algebras.
Keywords
Algebra; Eigenvalues and eigenfunctions; Polynomials; Terminology; Testing;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1986., 27th Annual Symposium on
Conference_Location
Toronto, ON, Canada
ISSN
0272-5428
Print_ISBN
0-8186-0740-8
Type
conf
DOI
10.1109/SFCS.1986.53
Filename
4568222
Link To Document