Relative complexity for computable presentations of the conventional linear order on the set of naturals (Q1876412)

The author studies the relationship between computable representations of the set of natural numbers with the conventional linear order. Two reducibility relations are introduced on the set of all such representations. Each of these relations determines a certain partially ordered set of degrees. The author considers some questions concerning the algebraic structure of these posets and the interlocation of various degrees. This is an English translation of the author's article [Mat. Tr. 5, No. 1, 114--128 (2002; Zbl 1009.03022)].