# 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$$?