But, this is a probabilistic algorithm which might fail. --Dan On Aug 19, 2014, at 9:22 PM, Victor Miller <victorsmiller@gmail.com> wrote:
The algorithm of Rajagoplan and Schulman is easy to describe. It has one-sided error: that is we fix and epsilon > 0. The algorithm runs in time log(1/epsilon)*n^2 (where n is the size of S), and will only fail with probability < epsilon (using random choices). Here's the algorithm:
Repeat the following log(1/epsilon) times:
Pick 3 independent formal combinations of elements of S with coefficients in Z mod 2. Call them a, b, c. Verify that a(bc) = (ab)c, where the multiplication is done via formal linear combinations.
If S isn't associative, with probability at least (1-epsilon)^log(1/epsilon) it will detect it this way.