Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes
- PDF / 1,233,044 Bytes
- 18 Pages / 439.642 x 666.49 pts Page_size
- 63 Downloads / 218 Views
Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes Bireswar Das1 · Shivdutt Sharma1 Accepted: 24 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The isomorphism problem for groups, when the groups are given by their Cayley tables is a well-studied problem. This problem has been studied for various restricted classes of groups. Kavitha gave a linear time isomorphism algorithm for abelian groups (JCSS 2007). Although there are isomorphism algorithms for certain nonabelian group classes represented by their Cayley tables, the complexities of those algorithms are usually super-linear. In this paper, we design linear and nearly linear time isomorphism algorithms for some nonabelian groups. More precisely, –
–
–
We design a linear-time algorithm to factor Hamiltonian groups. This allows us to obtain an O(n) algorithm for the isomorphism problem of Hamiltonian groups, where n is the order of the groups. We design a nearly linear time algorithm to find a maximal abelian direct factor of an input group. As a byproduct we obtain an O˜ (n) isomorphism for groups that can be decomposed as a direct product of a nonabelian group of bounded order and an abelian group, where n is the order of the groups. We observe that testing normality, computing the center of a group, finding a logarithmic sized generating set, computing quotient groups for groups given by their Cayley table could be done in linear or nearly linear time.
This article belongs to the Topical Collection: Special Issue on Computer Science Symposium in Russia (2019) Guest Editor: Gregory Kucherov A preliminary version of this article appeared in [7] . The current version is self-contained with the proofs of several propositions being added or rewritten along with reorganizations of some sections. Bireswar Das
[email protected] Shivdutt Sharma [email protected] 1
Indian Institute of Technology Gandhinagar, Gandhinagar, India
Theory of Computing Systems
Keywords Group isomorphism problem · Nearly linear time algorithms · Hamiltonian groups · Cayley table
1 Introduction Two groups (G, ·) and (H, ×) are said to be isomorphic if there exists a bijective function f : G −→ H , which is a homomorphism i.e. ∀a, b ∈ G, f (a · b) = f (a) × f (b). The decision version of this problem is to check whether two input groups (G, ·) and (H, ×) are isomorphic or not. There are multiple ways in which a group can be given as the input. Two of commonly used methods are by a generating set and by the Cayley table. The complexity of the group isomorphism problem varies with the input representation. In this paper we assume that input groups are given by their Cayley tables unless stated otherwise explicitly. Given two elements a and b, the Cayley table can return the product a · b in constant time. The inputs are assumed to be Cayley tables of groups and not just any arbitrary data1 . It is not known whether the group isomorphism problem (GrISO) is in P. If it is NP-complete then polynomial hierarch
Data Loading...
