Return to Revisions

For the general case (i.e. no restrictions on the set $\{ g_1,\ldots,g_n \}$), one cannot get a computable upper bound on the runtime of any algorithm for the dimension $m\geq 4$. It follows from the undecidability of the membership problem in $SL_4(\mathbb{Z})$ due to Mikhailova. If one had an algorithm with a computable upper bound for the running time, then we could run it on any matrix $g\in SL_m(\mathbb{Z})$ and stop if it takes longer than our bound. After that we could check if the output indeed gives a word such that $g=g_{i_1}g_{i_2}\ldots g_{i_s}$ and hence we would solve the membership problem.