Эта публикация цитируется в
1 статье
Сводимость почти полиномиальными функциями
С. С. Марченков Московский государственный университет им. М.В Ломоносова, Ленинские горы, д. 1, г. Москва, 119991, Россия
Аннотация:
Целью работы является введение варианта
$m$-сводимости с помощью почти полиномиальных функций и исследование образующегося частично упорядоченного множества
$\mathcal M_{\mathbb P}$ соответствующих степеней неразрешимости. Доказывается, что множество
$\mathcal M_{\mathbb P}$ имеет по крайней мере счетное число минимальных элементов, но не имеет максимальных элементов. Множество
$\mathcal M_{\mathbb P}$ не является ни верхней, ни нижней полурешеткой. Каждый элемент множества
$\mathcal M_{\mathbb P}$, отличный от наименьшего, можно включить в континуальную антицепь. Строится континуальное семейство попарно изоморфных начальных сегментов множества
$\mathcal M_{\mathbb P}$, имеющих счетную ширину и высоту и пересекающихся только по наименьшему элементу множества.
Ключевые слова:
$m$-сводимость, почти полиномиальные функции.
УДК:
510.531 Поступила: 01.02.2022
Исправленный вариант: 03.05.2022
Принята к публикации: 29.06.2022
DOI:
10.26907/0021-3446-2022-12-68-78