The algebraic structure of GapP and Hash P functions is introduced by formalizing them as power series ring and semiring, respectively. It is proved that for every invertible GapP function g, P/sup g/=P/sup 1/g/, and for all positive integers i, P/sup g/=P to the g/sup i/, power. Applying the Ladner theorem for functions, it is shown that P/sup s/=P/sup (s)/ for all S if and only if P=PP, where (S) is the subring generated by S. It also concluded that the class of rational series is contained in FP. Considering the group of all invertible functions, it is proved that all functions in the same coset with respect to FP are Turing equivalent, every Turing degree inside GapP except FP contains infinitely many cosets, and P not=PP if and only if the index of FP is infinite.
展开▼
机译：通过将GapP和Hash P函数分别形式化为幂级数环和半环来介绍它们的代数结构。事实证明，对于每个可逆的GapP函数g，P / sup g / = P / sup 1 / g /，对于所有正整数i，P / sup g / = P对g / sup i /，幂。将Ladner定理应用到函数上，表明当且仅当P = PP时，所有S的P / sup s / = P / sup（s）/，其中（S）是S生成的子环。有理数列的类别包含在FP中。考虑所有可逆函数的组，证明与FP处于同一陪集的所有函数都是图灵等效的，除了FP之外，GapP内除FP之外的每个Turing度都包含无限多个陪集，且P not = PP且仅当FP是无限的。
展开▼
