22.14 Transformation monoid minimisation

For every \(n \in \mathbb{N}\), the full transformation monoid \(T_n\) is the set of (total) functions from \(\{1,2,\ldots,n\}\) to \(\{1,2,\ldots,n\}\), equipped with the standard function composition. The symmetric group \(S_n\) is the subroup of \(T_n\) composed of all the permutations. What is the complexity of the following decision problems with respect to the parameter \(n\):

Problem 1: Given a submonoid \(\langle s_1,s_2\rangle \subseteq T_n\) generated by two elements, does there exist an integer \(m\) smaller than \(n\) such that \(\langle s_1,s_2\rangle\) can be embedded in \(T_m\)?

Problem 2: Given a subgroup \(\langle g_1,g_2\rangle \subseteq S_n\) generated by two elements, does there exist an integer \(m\) smaller than \(n\) such that \(\langle g_1,g_2\rangle\) can be embedded in \(S_m\)?