Abstract:
The aim of the work is to introduce a variant of $m$-reducibility using almost polynomial functions and to study the resulting partially ordered set $\mathcal M_{\mathbb P}$ of the corresponding degrees of undecidability. It is proved that the set $\mathcal M_{\mathbb P}$ has at least a countable number of minimal elements, but has no maximal elements. The set $\mathcal M_{\mathbb P}$ is neither an upper nor a lower semilattice. Each element of the set $\mathcal M_{\mathbb P}$, other than the smallest, can be included in a continuum antichain. We construct a continuum family of pairwise isomorphic initial segments of the set $\mathcal M_{\mathbb P}$, having a countable width and height and intersecting only by the smallest element of the set.
Keywords:$m$-reducibility, almost polynomial functions.
Fulltext:
PDF file (369 kB)