"Fast" obviously doesn't mean "polynomial" in this context, because the obvious check-all-triples procedure is just O(|S|^3). It's also clear that we can't do better than O(|S|^2), since that wouldn't give us time to check all the cells of the table, and an arbitrary table might contrive to screw us on the very last cell we checked, so we can't skimp -- the algorithm has to "consider" every cell. I propose that a preliminary definition of "fast" might be "anything faster than cubic". I guess I would be surprised if we couldn't do at least a *little* better. On Tue, Aug 19, 2014 at 9:02 PM, Henry Baker <hbaker1@pipeline.com> wrote:
I'm interested in binary operations on a finite set S that are associative, period; no other constraints.
1. Are there "fast" methods for checking associativity given the operation table?
2. Can all such associative operations be emulated "efficiently" using an isomorphism in which the operation is matrix multiplication (not just over standard rings, but extended like Knuth & the APL language do) ?
(RCS knows why I'm asking this question.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun