Suppose for each integer $n\geq 1$ we have a submonoid $M_n\subset \mathrm{Self}(\{1, \dots, n\})$ of self-maps of $\{1, \dots, n\}$.

Suppose we can decide whether a given self-map is an element of $M_n$ in polynomial time in $n$.

Suppose we can list all elements of $M_n$ in polynomial time in $|M_n|\times n$.

Then consider the problem of deciding whether a given element of $\{1, \dots, n\}$ lies in $M_n(1)$.

How large can its asymptotic worst case time complexity be?

Suppose for each integer $n\geq 1$ we have a submonoid $M_n\subset \mathrm{Self}(\{1, \dots, n\})$ of self-maps of $\{1, \dots, n\}$.

A characterization of $M_n$ is an algorithm that takes an integer $n\geq 1$ and a self-map of $\{1, \dots, n\}$ as input and decides whether the self-map lies in $M_n$.

A characterization of $M_n(1)$ is an algorithm that takes two integers $n\geq i\geq 1$ as input and decides whether $i$ lies in $M_n(1)$.

Suppose we have a characterization of $M_n$ that runs in polynomial time in $n$. Is there a characterization of $M_n(1)$ that runs in polynomial time in $n$?

Suppose for each integer $n\geq 1$ we have a submonoid $M_n\subset \mathrm{Self}(\{1, \dots, n\})$ of self-maps of $\{1, \dots, n\}$.

Suppose we can decide in polynomial time in $n$ whether a given self-map lies in $M_n$.

Then consider the problem of deciding whether a given element of $\{1, \dots, n\}$ lies in $M_n(1)$.

How large can its asymptotic worst case time complexity be?

Suppose for each integer $n\geq 1$ we have a submonoid $M_n\subset \mathrm{Self}(\{1, \dots, n\})$ of self-maps of $\{1, \dots, n\}$.

Suppose we can decide whether a given self-map is an element of $M_n$ in polynomial time in $n$.

Suppose we can list all elements of $M_n$ in polynomial time in $|M_n|\times n$.

Then consider the problem of deciding whether a given element of $\{1, \dots, n\}$ lies in $M_n(1)$.

How large can its asymptotic worst case time complexity be?