О способах характеризации полных множеств

Традиционный путь построения критериев полноты по сводимости – описание свойства ослабленной, вообще говоря, продуктивности дополнения полного по данной сводимости множества. Это свойство своим происхождением обязано сведению к полному множеству креативного множества. Такой путь апеллирует непосредственно к универсальности креативного множества в классе всех рекурсивно перечислимых.
Однако для ряда сводимостей полноту рекурсивно перечислимого множества можно констатировать на основе факта сведения к нему множества степени ниже степени креативного множества. Такое пробное множество, конечно, не рекурсивно перечислимо. При этом место свойства эффективной не рекурсивной перечислимости, как у продуктивно- го множества, могут занимать варианты свойства диагональной нерекурсивности, но не для всех сводимостей.
В статье рассматривается связь этих двух подходов, в частности, связь различных ослаблений свойства продуктивности с диагональной нерекурсивностью, и результаты, получаемые этими способами для тьюринговых и табличных сводимостей.