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)$?
No comments:
Post a Comment