8
$\begingroup$

This question is related to this one . Let $G$ be a finitely generated subgroup of $GL_n(K)$ for some field $K$ of characteristic 0. Then $G$ is a linear group over $\mathbb{Q}(x_1,...,x_m)$, the field of rational functions over $\mathbb{Q}$. This follows from the fact that one can assume $K$ to be a finitely generated field, which is a finite extension of the field $\mathbb{Q}(x_1,...,x_m)$, and one can get rid of the finite extension by considering matrices of bigger size.

Question. What is the maximal possible computational complexity of the word problem in such $G$?

It seems clear that the complexity always is at most co-NP (one can check that a product of matrices with entries rational functions is not equal to 1 by plugging not very large values for the variables $x_1,...,x_m$ and computing the product of matrices over $\mathbb{Q}$. Is co-NP the best we can get in general (assuming $m\ge 2$, $n\ge 3$)?

$\endgroup$
6
$\begingroup$

The word problem is in deterministic logspace for linear groups, so it is very fast! See Word problems solvable in logspace by Lipton and Zalcstein, J. Assoc. Comput. Mach. 24 (1977), no. 3, 522–526.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Here is a link dl.acm.org/… $\endgroup$ – Benjamin Steinberg Nov 10 '11 at 2:21
  • 1
    $\begingroup$ According to Markus Lohrey, the compressed word problem for linear groups is in coRP. That means there is a polynomial time probabilistic Turing machine which says No if the element is not the identity and gets Yes correct at least half the time. It is believed coRP is smaller than NP so even the compressed word problem is good. $\endgroup$ – Benjamin Steinberg Nov 10 '11 at 2:39
  • $\begingroup$ The above comment is more relevant to your previous question since the proof uses the randomized polytime algorithm to check if a polynomial is 0. $\endgroup$ – Benjamin Steinberg Nov 10 '11 at 3:34
  • 1
    $\begingroup$ In math.stevens.edu/~rgilman/ccny/other.pdf Bob Gilman gives two more references. $\endgroup$ – user6976 Nov 10 '11 at 4:03
  • 4
    $\begingroup$ Also in our survey with Olga Kharlampovich, it is written that the word problem in every matrix group is decidable in polynomial time. But I forgot why we wrote that and there is no reference there. $\endgroup$ – user6976 Nov 10 '11 at 4:09

Your Answer

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