3
$\begingroup$

$\DeclareMathOperator\GL{GL}$Suppose $G$ is a subgroup of $\GL(n,q)$ given by a list of generators. What is known about the complexity of the corresponding "membership problem", that is, the problem of deciding whether a given $g \in \GL(n,q)$ belongs to $G$ ?

While it would be great to have an actual bound on the complexity, or to know that some other problems reduce to this one, I would also be happy with empirical or even anecdotal evidence.

To me, it seems that the problem is very tractable when $n$ is less than 10 and $q$ is less than 50, but becomes hard very very rapidly. I think trying to compute with $\GL(25, 81)$ would be a disaster. What about $n\ge 500$ and $p\ge 10,000$ ?

Improve this question
$\endgroup$
1
  • $\begingroup$ I think it's in $\text{NP}\cap\text{coNP}$, see this MO answer. $\endgroup$ Commented Feb 22, 2024 at 16:07

1 Answer 1

Reset to default
7
$\begingroup$

$\DeclareMathOperator\GL{GL}$As pointed out in the intro to Babai–Beals–Seress STOC '09 constructive membership testing—i.e., not just telling whether $g$ belongs to $G$, but furthermore writing $g$ as a word in the given generators if it does — encounters "number theoretic obstacles" to its complexity:

  • in $\GL_1(q)$ it is the discrete log problem, widely used in cryptography, though there has been some recent progress on algorithms for it).
  • For diagonal subgroups of $\GL_2(q)$ it is the decisional Diffie–Hellman problem, another standard problem in cryptography.

So already in those low-dimensional cases as $q$ gets large, the current state of the art will not be efficient.

However, those are in some sense "the only" obstacles, in that Babai–Beals–Seress (ibid.) show that with oracles for factoring and discrete log, one can then solve constructive membership in matrix groups by a Las Vegas polynomial-time algorithm.

Improve this answer
$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.