<p>First, is it a group at all?  A fundamental problem is checking whether a given operation (in table form) is associative.  The obvious approach is cubic time, <a href="https://doi.org/10.1137/S0097539797325387" rel="nofollow noreferrer">Rajagopalan and Schulman</a> do it in near-quadratic time.</p>

CC BY-SA 3.0
2018-03-20T18:23:31.640Z
2018-03-20T18:23:31.640Z
mic
<p>The following <a href="https://ac.els-cdn.com/S0022000001917647/1-s2.0-S0022000001917647-main.pdf?_tid=302eefa0-7103-4a2e-9c56-995ef32205dd&amp;acdnat=1522639441_71414ea1430b72bbb3a792f00c286e65" rel="nofollow noreferrer">paper</a> by Barrington-Kadau-McKenzie-Lange studies the Cayley Group Membership problem (CGM): given a group as a multiplication table, a subset of elements $X$ and an element $t$ determine if $t$ is in the subgroup generated by $X$. They show that CGM(nilpotent) is in the complexity class FO($(\log\log{n})^2$) which provably does not contain parity and is therefore not hard for any class containing parity (such as ACC$^0$, NC$^1$,L,NL etc.). This class is also not known to be contained in any of these aforementioned classes. Thus they establish that these problems are somehow orthogonal to the usual small complexity classes.</p>

CC BY-SA 3.0
2018-04-02T03:38:05.020Z
2018-04-02T03:38:05.020Z
SamiD
<p>Cameron and Wu investigated several algorithmic problems for groups, <a href="https://www.sciencedirect.com/science/article/pii/S0012365X09001289" rel="nofollow noreferrer">The complexity of the weight problem for permutation and matrix groups</a>. They proved NP-completeness for some of them.</p>

CC BY-SA 3.0
2018-03-16T07:48:38.433Z
2018-03-16T07:48:38.433Z
Mohammad Al-Turkistany
<p>I am currently reading about research problems in nilpotent groups ( assume table representation ). As we know that solvable group isomorphism is known to be in the (almost ) intersection of $\mathcal{NP}$ and $\text{co}\mathcal{NP}$ and even for groups whose derived series has length two, we don't how to do isomorphism in $\mathcal{NP}$ $\cap$ $\text{co}\mathcal{NP}$. </p>

<p><strong>Question 1 :</strong> What are the interesting algorithmic questions to answer about nilpotent group class or its sub-class   ( which is non-abelian ) <em>other than isomorphism problem</em>?</p>

<p><strong>Question 2 :</strong>  What are interesting questions to answer about groups when given in the table representation <em>other than isomorphism</em>? A non-interesting question is to find the <strong>intersection</strong> of two group or to find the order of any element. Testing <strong>membership</strong> is also not interesting as the input given is a table.</p>

CC BY-SA 3.0
2018-03-16T14:34:42.330Z
Cross-posted to https://mathoverflow.net/q/295368
Emil Jeřábek
<soft-question><gr.group-theory>
What are interesting algorithmic questions for groups in table representation?
alha hu
# What are interesting algorithmic questions for groups in table representation?

(Asked by: username_0 on 2018-03-16)

I am currently reading about research problems in nilpotent groups ( assume table representation ). As we know that solvable group isomorphism is known to be in the (almost ) intersection of $\mathcal{NP}$ and $\text{co}\mathcal{NP}$ and even for groups whose derived series has length two, we don't how to do isomorphism in $\mathcal{NP}$ $\cap$ $\text{co}\mathcal{NP}$.

**Question 1 :** What are the interesting algorithmic questions to answer about nilpotent group class or its sub-class ( which is non-abelian ) *other than isomorphism problem*?

**Question 2 :** What are interesting questions to answer about groups when given in the table representation *other than isomorphism*? A non-interesting question is to find the **intersection** of two group or to find the order of any element. Testing **membership** is also not interesting as the input given is a table.

**Tags:** soft-question, gr.group-theory
> **Comments:**
> **username_1**: Cross-posted to https://mathoverflow.net/q/295368  

---

## 3 answers

### Answer by username_2 on 2018-03-20. Score: 4

First, is it a group at all? A fundamental problem is checking whether a given operation (in table form) is associative. The obvious approach is cubic time, [Rajagopalan and Schulman](https://doi.org/10.1137/S0097539797325387) do it in near-quadratic time.


---

### Answer by username_3 on 2018-04-02. Score: 2

The following [paper](https://ac.els-cdn.com/S0022000001917647/1-s2.0-S0022000001917647-main.pdf?_tid=302eefa0-7103-4a2e-9c56-995ef32205dd&acdnat=1522639441_71414ea1430b72bbb3a792f00c286e65) by Barrington-Kadau-McKenzie-Lange studies the Cayley Group Membership problem (CGM): given a group as a multiplication table, a subset of elements $X$ and an element $t$ determine if $t$ is in the subgroup generated by $X$. They show that CGM(nilpotent) is in the complexity class FO($(\log\log{n})^2$) which provably does not contain parity and is therefore not hard for any class containing parity (such as ACC$^0$, NC$^1$,L,NL etc.). This class is also not known to be contained in any of these aforementioned classes. Thus they establish that these problems are somehow orthogonal to the usual small complexity classes.


---

### Answer by username_4 on 2018-03-16. Score: 1

Cameron and Wu investigated several algorithmic problems for groups, [The complexity of the weight problem for permutation and matrix groups](https://www.sciencedirect.com/science/article/pii/S0012365X09001289). They proved NP-completeness for some of them.


---

