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 $n\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 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.