Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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