|
Reducibility by means of almost polynomial functions
S. S. Marchenkov Moscow State University, 1 Leninskie Gory, Moscow, 119991 Russia
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.
Received: 01.02.2022 Revised: 03.05.2022 Accepted: 29.06.2022
Citation:
S. S. Marchenkov, “Reducibility by means of almost polynomial functions”, Izv. Vyssh. Uchebn. Zaved. Mat., 2022, no. 12, 68–78; Russian Math. (Iz. VUZ), 66:12 (2022), 62–70
Linking options:
https://www.mathnet.ru/eng/ivm9837 https://www.mathnet.ru/eng/ivm/y2022/i12/p68
|
Statistics & downloads: |
Abstract page: | 76 | Full-text PDF : | 24 | References: | 21 | First page: | 4 |
|