Reducibility by means of almost polynomial functionsстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 26 июня 2024 г.
Аннотация:Целью работы является введение варианта m-сводимости с помощью почти полиномиальных функций и исследование образующегося частично упорядоченного множества M_P соответствующих степеней неразрешимости. Доказывается, что множество M_P имеет по крайней мере счетное число минимальных элементов, но не имеет максимальных элементов. Множество M_P не является ни верхней, ни нижней полурешеткой. Каждый элемент множества M_P, отличный от наименьшего, можно включить в континуальную антицепь. Строится континуальное семейство попарно изоморфных начальных сегментов множества M_P, имеющих счетную ширину и высоту и пересекающихся только по наименьшему элементу множества.