5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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 do it in near-quadratic time.

$\endgroup$
2
$\begingroup$

The following paper 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.

$\endgroup$
1
$\begingroup$

Cameron and Wu investigated several algorithmic problems for groups, The complexity of the weight problem for permutation and matrix groups. They proved NP-completeness for some of them.

$\endgroup$

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.