What's the complexity of factoring over a set of generators (say in $GL_2$)?

Question

In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL_2(k)$ do we know the time complexity of factoring it into a product of $A$s and $B$s is (or showing that such a factorization does not exist); that is, how long would it take to exhibit the product (or show the lack of existence)

$$ABBAAAB\cdots BAAB = C?$$

I have a feeling that this falls under Ladner's theorem but I'm not sure.

Answer 1

This is usually called the (constructive) membership problem (rather than a "factorization" problem). The membership problem is to decide whether $C \in \langle A,B \rangle$; the constructive membership problem is to actually find a word (if any) in $A,B$ that equals $C$.

Its complexity may depend on whether you want to allow $A^{-1}, B^{-1}$ in your word (in which case it is the membership problem for a subgroup of a general linear group) or not (in which case it is the membership problem for a submonoid or subsemigroup of a general linear group).

I don't know a complete answer to your question, but here are some special cases and hopefully relevant references:

• In general, the membership problem in linear groups over infinite fields is undecidable [Mihailova, 1968]. I do not know whether undecidability holds for the case of 2-generated subgroups.

• The Tits alternative implies that the group generated by $A,B$ is either solvable-by-finite, or contains a nonabelian free group. The intro of Eick-Kirschmer-Leedham-Green contains pointers to algorithms that solve the Tits alternative for subgroup of $GL_n(\mathbb{Q})$, in the sense of deciding which of the two cases holds.

• In the solvable-by-finite case, the membership problem is decidable [Kopytov, 1968].

• In the free case less is known. Eick, Kirschmer, and Leedham-Green ("The constructive membership problem for discrete free subgroups of rank 2 of $SL_2(\mathbb{R})$") give an efficient-in-practice algorithm for 2-generated subgroups of $SL_2(\mathbb{R})$ that are not only free but also discrete.

• If $A,B$ commute, then Cai-Lipton-Zalcstein [FOCS 1994] show how to solve even the constructive subsemigroup membership problem in P. If $A,B$ don't commute, it's not even clear to me whether your problem is in NP, as it's not obvious to me that the desired word is polynomial-length nor has a polynomial-length description.

• See also the final report of a 2014 Banff workshop on algorithms for linear groups.

(PS - If by "falls under Ladner's theorem" you mean "is likely to be NP-intermediate" (in the sense of being in NP but neither being in P nor being NP-complete), that's an unusual phrase, but I know what you meant. But, in case you're not aware, essentially no natural problem is known to have this status, even under standard complexity assumptions (such as PH not collapsing). See here for a list of natural problems that are currently candidates for being NP-intermediate.)