$m$-Reducibility with Upper and Lower Bounds for the Reducing Functions
Matematičeskie zametki, Tome 70 (2001) no. 1, pp. 12-21
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
We study pairs $(\mathfrak T^1,\mathfrak T^0)$ of classes of nondecreasing total one-place arithmetic functions that specify reflexive and transitive binary relations $\{(A,B)\mid A,B\subseteq N\mathop{\&}(\exists$ g.r.f. $h$) $(\exists f_1\in \mathfrak T^0)[A\le{}_m^hB\mathop{\&}f_0\trianglelefteq h\trianglelefteq f_1]\}$. (Here $k\trianglelefteq 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.
[1] Bulitko V. K., “Subtyuringovy svodimosti ogranichennoi slozhnosti”, Izv. vuzov. Matem., 1992, no. 1, 27–37 | MR | Zbl
[2] Bulitko V. K., “About Segment Complexity of Turing Reductions”, Math. Log. Quart., 45:4 (1999), 561–571 | MR | Zbl
[3] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972 | MR
[4] Bulitko V. K., “O rekursivno szhimaemykh mnozhestvakh”, Matem. zametki, 64:1 (1998), 9–16 | MR | Zbl