Bounded reducibility for computable numberings.

Nikolay Bazhenov, Manat Mustafa, Sergey Ospichev

Research output: Contribution to journalArticle

Abstract

The theory of numberings gives a fruitful approach to studying uniform computations for various families of mathematical objects. The algorithmic complexity of numberings is usually classified via the reducibility $\leq$ between numberings. This reducibility gives rise to an upper semilattice of degrees, which is often called the Rogers semilattice. For a computable family $S$ of c.e. sets, its Rogers semilattice $R(S)$ contains the $\leq$-degrees of computable numberings of $S$. Khutoretskii proved that $R(S)$ is always either one-element, or infinite. Selivanov proved that an infinite $R(S)$ cannot be a lattice.

We introduce a bounded version of reducibility between numberings, denoted by $\leq_{bm}$. We show that Rogers semilattices $R_{bm}(S)$, induced by $\leq_{bm}$, exhibit a striking difference from the classical case. We prove that the results of Khutoretskii and Selivanov cannot be extended to our setting: For any natural number $n\geq 2$, there is a finite family $S$ of c.e. sets such that its semilattice $R_{bm}(S)$ has precisely $2^n-1$ elements. Furthermore, there is a computable family $T$ of c.e. sets such that $R_{bm}(T)$ is an infinite lattice.
Original languageEnglish
Article number1
Pages (from-to)1
Number of pages12
JournalLecture Notes in Computer Science
Publication statusPublished - Jun 19 2019

Fingerprint

Reducibility
Semilattice
Algorithmic Complexity
Natural number
Family

Cite this

Bounded reducibility for computable numberings. / Bazhenov, Nikolay; Mustafa, Manat; Ospichev, Sergey.

In: Lecture Notes in Computer Science, 19.06.2019, p. 1.

Research output: Contribution to journalArticle

@article{33fe1f60ea4e4d07954bb0c0a2810529,
title = "Bounded reducibility for computable numberings.",
abstract = "The theory of numberings gives a fruitful approach to studying uniform computations for various families of mathematical objects. The algorithmic complexity of numberings is usually classified via the reducibility $\leq$ between numberings. This reducibility gives rise to an upper semilattice of degrees, which is often called the Rogers semilattice. For a computable family $S$ of c.e. sets, its Rogers semilattice $R(S)$ contains the $\leq$-degrees of computable numberings of $S$. Khutoretskii proved that $R(S)$ is always either one-element, or infinite. Selivanov proved that an infinite $R(S)$ cannot be a lattice.We introduce a bounded version of reducibility between numberings, denoted by $\leq_{bm}$. We show that Rogers semilattices $R_{bm}(S)$, induced by $\leq_{bm}$, exhibit a striking difference from the classical case. We prove that the results of Khutoretskii and Selivanov cannot be extended to our setting: For any natural number $n\geq 2$, there is a finite family $S$ of c.e. sets such that its semilattice $R_{bm}(S)$ has precisely $2^n-1$ elements. Furthermore, there is a computable family $T$ of c.e. sets such that $R_{bm}(T)$ is an infinite lattice.",
author = "Nikolay Bazhenov and Manat Mustafa and Sergey Ospichev",
year = "2019",
month = "6",
day = "19",
language = "English",
pages = "1",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Bounded reducibility for computable numberings.

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - Ospichev, Sergey

PY - 2019/6/19

Y1 - 2019/6/19

N2 - The theory of numberings gives a fruitful approach to studying uniform computations for various families of mathematical objects. The algorithmic complexity of numberings is usually classified via the reducibility $\leq$ between numberings. This reducibility gives rise to an upper semilattice of degrees, which is often called the Rogers semilattice. For a computable family $S$ of c.e. sets, its Rogers semilattice $R(S)$ contains the $\leq$-degrees of computable numberings of $S$. Khutoretskii proved that $R(S)$ is always either one-element, or infinite. Selivanov proved that an infinite $R(S)$ cannot be a lattice.We introduce a bounded version of reducibility between numberings, denoted by $\leq_{bm}$. We show that Rogers semilattices $R_{bm}(S)$, induced by $\leq_{bm}$, exhibit a striking difference from the classical case. We prove that the results of Khutoretskii and Selivanov cannot be extended to our setting: For any natural number $n\geq 2$, there is a finite family $S$ of c.e. sets such that its semilattice $R_{bm}(S)$ has precisely $2^n-1$ elements. Furthermore, there is a computable family $T$ of c.e. sets such that $R_{bm}(T)$ is an infinite lattice.

AB - The theory of numberings gives a fruitful approach to studying uniform computations for various families of mathematical objects. The algorithmic complexity of numberings is usually classified via the reducibility $\leq$ between numberings. This reducibility gives rise to an upper semilattice of degrees, which is often called the Rogers semilattice. For a computable family $S$ of c.e. sets, its Rogers semilattice $R(S)$ contains the $\leq$-degrees of computable numberings of $S$. Khutoretskii proved that $R(S)$ is always either one-element, or infinite. Selivanov proved that an infinite $R(S)$ cannot be a lattice.We introduce a bounded version of reducibility between numberings, denoted by $\leq_{bm}$. We show that Rogers semilattices $R_{bm}(S)$, induced by $\leq_{bm}$, exhibit a striking difference from the classical case. We prove that the results of Khutoretskii and Selivanov cannot be extended to our setting: For any natural number $n\geq 2$, there is a finite family $S$ of c.e. sets such that its semilattice $R_{bm}(S)$ has precisely $2^n-1$ elements. Furthermore, there is a computable family $T$ of c.e. sets such that $R_{bm}(T)$ is an infinite lattice.

M3 - Article

SP - 1

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

M1 - 1

ER -