Nondeterministic 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 . However, it is already known that the problem is in , so this is not really new information.|
|Running time||times the time taken for group operations.|
|Competing algorithms|| black-box group algorithm for abelianness testing: takes time times the time for group operations, but is deterministic.|
randomized black-box group algorithm for abelianness testing: takes polylog time (much faster) and is random, but provides proof only for non-abelianness, not for abelianness (i.e., only puts the problem in co-RP and not in RP).
Idea and outline
The idea is to apply the conversion of black-box group algorithm dependent on generating set to nondeterministic black-box group algorithm to the black-box group algorithm for abelianness testing given a generating set.