Testing commutativity of a group and the power of randomization
Testing commutativity of a group and the power of randomization
Abstract Let G be a group generated by k elements, G =〈 g 1 ,…, g k 〉, with group operations (multiplication, inversion and comparison with identity) performed by a black box. We prove that one can test whether the group G is abelian at a cost of O ( …