Диофантова сложность

Хорошо известно, что любое рекурсивно перечислимое множество $S$ натуральных чисел может быть представлено формулами следующих видов: $a\in S\Leftrightarrow \exists x\,\forall y\leqslant x\,\exists z_1,\dots,z_n$ ($D(a,x,y,z_1,\dots,z_n)=0$) (нормальная форма Дейвиса), $a\in S\Leftrightarrow \exists z_1,\dots,z_n$ ($E_1(a,z_1,\dots,z_n)=E_2(a,z_1,\dots,z_n)$) (экспоненциально диофантово представление) и $a\in S\Leftrightarrow \exists z_1,\dots,z_n$ ($D(a,z_1,\dots,z_n)=0$) (диофантово представление). Каждое из этих трех представлений позволяет ввести различные меры сложности множества $S$ как целого и сложности распознавания принадлежности к $S$ его отдельных элементов. В работе дается обзор некоторых результатов по таким мерам сложности, полученных различными авторами. Библ. – 26 назв.