СИБИРСКИЙ МАТЕМАТИЧЕСКИЙ ЖУРНАЛ

АННОТАЦИИ

Исследуются различия $Q$-сводимости и $m$-сводимости на
вычислимо перечислимых множествах. Строится такое не вычислимое не $m$-полное
вычислимо перечислимое множество $B$, что для всех вычислимо перечислимых
множеств $A\leq_QB$ выполняется $A\leq_mB$. Доказывается, что для любого не
вычислимого вычислимо перечислимого множества $A$ существует такое вычислимо
перечислимое множество $B$, что $A\leq_QB$, но $A\not\leq_mB$. Доказывается, что
для любого простого множества $B$ существует такое вычислимо перечислимое
множество $A$, что $A\leq_QB$, но $A\not\leq_mB$. Из последнего результата, в
частности, следует, что в $Q$-степени любого простого множества содержится
бесконечно много в.~п. $m$-степеней.