m-Reducibility with Upper and Lower Bounds for the Reducing Functions |
| |
Authors: | Belyaev V N Bulitko V K |
| |
Institution: | 1. I. I. Mechnikov Odessa State University, Russia
|
| |
Abstract: | We study pairs $\left( {\mathfrak{T}^1 ,\mathfrak{T}^0 } \right)$ of classes of nondecreasing total one-place arithmetic functions that specify reflexive and transitive binary relations $$\left\{ {\left( {A,B} \right)\left| {A,B \subseteq N\& \left( {\exists g.r,fh} \right)\left( {\exists f_1 \in \mathfrak{T}^0 } \right)\left {A \leqslant _m^h B\& f_0 \underline \triangleleft h\underline \triangleleft f_1 } \right]} \right.} \right\}$$ . (Here $k\underline \triangleleft {\kern 1pt} {\kern 1pt} {\kern 1pt} l$ means that the function l majorizes the function k almost everywhere.) Criteria for reflexivity and transitivity of such relations are established. Evidence of extensive branching of the arising system of bounded m-reducibilities is obtained. We construct examples of such reducibilities that essentially differ from the standard m-reducibility in the structure of systems of undecidability degrees that they generate and in the question of completeness of sets. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|