This article is cited in 1 paper

$m$-Reducibility with Upper and Lower Bounds for the Reducing Functions

V. N. Belyaev, V. K. Bulitko

I. I. Mechnikov Odessa National University

Abstract: 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.

UDC: 517.1

Received: 07.02.2000

DOI: 10.4213/mzm713

 English version: Mathematical Notes, 2001, 70:1, 11–19

Bibliographic databases:

• 
• 
•