Given a binary function $f: [1..n] \times [1..n] \to [1..n]$ how to check that this operation is a group operation on $[1..n]$?


It's obvious that this can be done in $O(n^3)$ time just by checking all group properties. The most time-expensive property is associativity. Also it's clear that it could not be done faster than $O(n^2)$ time since you should at least examine all values $f(i,j)$.


The question is if there is any algorithm to solve this problem in time faster than $O(n^3)$?



Checking whether given binary operation is a group operation
See this entry - <http://rjlipton.wordpress.com/2010/06/03/an-amplification-trick-and-stoc-2010/> for a nice discussion on the question you have posed and other related ones. The article also has links to the original papers.


