9
$\begingroup$

Given a binary operation specified as an $n \times n$ Cayley table, what is the complexity of the best deterministic algorithm for testing if the binary operation is a group?

There's a fairly simple deterministic $O(n^2 \log n)$ algorithm which works as follows. We can check if the binary operation is a quasigroup in $O(n^2)$ time by verifying the Latin square property. It is also easy to determine if the group has an identity element in $O(n^2)$ time. Quasigroups have generating sets of size at most $\log_2 n$ and such a generating set can be found in $O(n^2)$ time using a simple greedy algorithm. Applying Light's associativity test then allows us to test associativity in $O(n^2 \log n)$ time.

An obvious lower bound is $\Omega(n^2)$. According to wikipedia, there is a randomized BPP algorithm for testing associativity in $O(n^2)$, so this bound is tight for BPP algorithms.

Is there a deterministic $O(n^2)$ algorithm as well?

$\endgroup$
2
  • 1
    $\begingroup$ The input is $n^2\log n$ bits - so you're asking for a sublinear algorithm? I couldn't access the Rajagopalan-Schulman BPP algorithm paper so don't know what their computational model is. $\endgroup$
    – Dap
    Nov 10, 2017 at 8:03
  • $\begingroup$ @Dap No, it would be a linear time algorithm. In this model, one typically assumes group operations and things like equity testing can be done in constant time. Think of each group element as using one unit of memory. $\endgroup$
    – Qudit
    Nov 10, 2017 at 8:10

1 Answer 1

0
$\begingroup$

It was shown only recently that testing whether a Latin Square is a group takes time $O(n^{2} \log^{c} n) = \tilde{O}(n^2)$ (the $\tilde{O}$ hides the polylogarithmic factor).

https://arxiv.org/pdf/2011.03133.pdf

$\endgroup$
1
  • $\begingroup$ That is an interesting paper but I don't think it is directely relevant to the question above. The algorithm that the authors give is in the Turing machine model whereas here I am considering the more usual RAM machine model. Presumably, this difference is the reason for the extra log factors in the paper. Also , I guess you meant $\tilde{O}(n^2)$ instead of $\tilde{O}(n)$. $\endgroup$
    – Qudit
    May 15 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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