14
$\begingroup$

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)$?

$\endgroup$

2 Answers 2

13
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

Indeed, S. Rajagopalan and L. Schulman prove that this can be done in $O(n^2\log n)$ time in the paper "Verifying identities" from the proceedings of the 37th annual symposium on foundations of computer science. Their algorithm is applied to operations with cancellative properties, but checking if a binary operation has the cancellative property can be done in $O(n^2)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.