Конечная порождаемость некоторых групп рекурсивных перестановок

Пусть класс $\mathcal Q$ функций натурального аргумента замкнут относительно суперпозиции и содержит тождественную функцию. Множество перестановок $f$ таких, что $f,f^{-1}\in\mathcal Q$, образует группу (относительно операции композиции), которую будем обозначать $Gr(\mathcal Q)$. В работе доказана конечная порождаемость $Gr(\mathcal Q)$ для большого семейства классов $\mathcal Q$, удовлетворяющих определенным требованиям. В качестве примера рассмотрен класс $\mathrm{FP}$ функций, вычислимых за полиномиальное время на машине Тьюринга. Полученный результат обобщается на классы $\mathscr E^n$ иерархии Гжегорчика, $n\geq2$.
Кроме того, для рассматриваемых классов $\mathcal Q$ определено минимальное число перестановок, порождающих группу $Gr(\mathcal Q)$, равное двум. Точнее, получен более сильный результат: существуют две перестановки из данной группы, композициями которых можно получить любую перестановку этой группы.
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 06–01–00438.