9
$\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$)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
8
$\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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Here is a link dl.acm.org/… $\endgroup$
    – Benjamin Steinberg
    Commented Nov 10, 2011 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
    Commented Nov 10, 2011 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
    Commented Nov 10, 2011 at 3:34
  • 1
    $\begingroup$ In math.stevens.edu/~rgilman/ccny/other.pdf Bob Gilman gives two more references. $\endgroup$
    – user6976
    Commented Nov 10, 2011 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
    Commented Nov 10, 2011 at 4:09

You must log in to answer this question.