1
$\begingroup$

Definition : An abelian group is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written

Input : Two finite abelian groups $|G| =n$ and $|H|=n$ by their table representation

Find : Is $G \cong H$?

There is an $O(n)$ running time algorithm for this problem, due to Kavitha [1].

Question : Is this problem known to be in Log Space?

I tried to google but did not get anything related to log space.


[1] T. Kavitha, Linear time algorithms for Abelian group isomorphism and related problems. Journal of Computer and System Sciences 73(6):986–996. (Science Direct)

$\endgroup$
2
$\begingroup$

The finite abelian group-isomorphism when groups are given in the form of multiplication tables known to be in $L$ and in $TC^0 (FOLL)$. For more detail you can see the thesis of the Dr. Fabian.

PhD Thesis of Dr. Fabian ( see page number 180 and 185 )

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.