Bruteforce blackbox group algorithm for abelianness testing
From Groupprops
Contents
Summary
Item  Value 

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 polynomialtime algorithm for it. 
Running time  ( times the time taken for group operations) + (time taken for enumerating all group elements) 
Blackbox group operations used  Group multiplication and an enumeration of all group elements, either as an algorithm or given explicitly. An explicit membership test is not required, though a full enumeration obviously gives a membership test as well, albeit not a very efficient one. 
Competing algorithms  generating setbased blackbox group algorithm for abelianness testing: This is faster, but more complicated to code. It proceeds by first finding a generating set for the group using the blackbox group algorithm for small generating setfinding problem, then applies the blackbox group algorithm for abelianness testing given a generating set.A smarter version combines the algorithms somewhat but yields no bigoh improvement. nondeterministic blackbox 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 blackbox 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 nonabelian, and a Yes answer means it is probably abelian, with the tradeoff between probability and the constant independent of . 
Parallelizable version  The algorithm can be massively parallelized as long as the blackbox group operations can be simultaneously accessed by multiple parallel processes. With massive parallelization, the time taken by the algorithm could be pushed down to , with the simply representing the time costs of managing the parallel processes. 
Idea and outline
The idea is simple: for every pair of elements of , compute the products and and check whether they are equal.
Analysis of complexity
Analysis of running time
The number of pairs is and we assume that traversal of the pairs does not change the order of magnitude. The cost of checking each pair is twice the cost of multiplication plus the cost of equality checking. With the logsize assumption, these are all polynomial in , so we get as the total time for the algorithm.
Summary
Complexity measure  Precise value  Order (bigoh notation) 

Query complexity for group multiplication i.e., number of times group multiplication is invoked, assuming an enumeration of elements is already available  (if we skip each element with itself) (if we skip all the pairs involving the identity element and all pairs of an element with itself) 

Active workspace required, assuming the enumeration of elements is available on two separate oneway readable tapes  enough to store finitely many group elements, and store location on tapes. All are logarithmic in . 