Polynomial-time isomorphism testing of groups of most finite orders

MaRDI QIDQ6303401zbMATH OpenFDO

Authors Heiko Dietrich, James B. Wilson

Publication date 22 June 2018

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) General theory for finite permutation groups (20B05) Automorphisms, homomorphisms, endomorphisms, etc. for abelian groups (20K30)

Abstract: [PLEASE SEE COMMENT] We consider the isomorphism problem for finite abelian groups and finite meta-cyclic groups. We prove that for a dense set of positive integers $n$, isomorphism testing for abelian groups of black-box type of order $n$ can be done in time polynomial in $logn$. We also prove that for a dense set of orders $n$ with given prime factors, one can test isomorphism for coprime meta-cyclic groups of black-box type of order $n$ in time polynomial in $logn$. Prior methods for these two classes of groups have running times exponential in $logn$.

This page was built for publication: Polynomial-time isomorphism testing of groups of most finite orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6303401)