.png){kind=icon}
.png){kind=icon}
Return
Testing Whether a Table Defines a Group
.png){kind=icon}
PRE
AI
DOI：10.1080/00029890.2025.2557077.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We consider the problem of testing whether a given n x n table for a binary operation * defines a group. The existence of an identity element 1 is readily checked. Likewise, we can quickly verify that elements possess inverses. The apparent bottleneck is to test associativity, which naively seems to require checking (x * y) * z = x * (y * z) for all n(3) triples (x, y, z). We show that n(2) + O (n log(2) n) carefully selected triples suffice to either prove that the table defines a group or to find a triple violating associativity. The bookkeeping cost of selecting which triples to check is O(n(2)), linear in the input length.
Keywords:
group testing
associativity
binary operation
algorithm
computational complexity
Journal
A
IF:
0.4
Papers:
111
Citations:
0