Generating set-based black-box group algorithm for abelianness testing
|Problem being solved||abelianness testing problem: determine whether a given group is abelian|
|Input format||a finite group given via an encoding of a group|
|Output format|| Yes/No depending on whether is abelian|
In the No case it is also possible to output a pair of elements that do not commute.
|Theoretical significance||This shows that the abelianness testing problem is in by explicitly finding a polynomial-time algorithm for it.|
|Running time||times the time taken for group operations (multiplication, equality checking).|
|Competing algorithms|| brute-force black-box group algorithm for abelianness testing: This is slower, but much easier to code and also much easier to parallelize. It checks all pairs of elements|
nondeterministic black-box group algorithm for abelianness testing: nondeterministic algorithm that first guesses a generating set, then verifies that it generates the whole group and that the elements in the generating set commute with each other. Takes time times the time taken for group operations.
randomized black-box group algorithm for abelianness testing: Takes time plus the time for group operations, assuming that lookup of random elements takes logarithmic time. The idea is to randomly select pairs of elements in the group and check whether they commute. A No answer means the group is definitely non-abelian, and a Yes answer means it is probably abelian, with the trade-off between probability and the -constant independent of .
Idea and outline
The algorithm combines two algorithms:
- It first finds a generating set of size at most using the black-box group algorithm for small generating set-finding problem. The time taken for this is times the time for group operations.
- It then applies the black-box group algorithm for abelianness testing given a generating set.