Generating set-based black-box group algorithm for abelianness testing
From Groupprops
Summary
Item | Value |
---|---|
Problem being solved | abelianness testing problem: determine whether a given group is abelian |
Input format | a finite group ![]() |
Output format | Yes/No depending on whether ![]() 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 ![]() |
Running time | ![]() |
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 ![]() randomized black-box group algorithm for abelianness testing: Takes time ![]() ![]() ![]() |
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.