Диофантова иерархия

Класс языков $\mathrm D$, определённый в работе L. Adelman и K. Manders (1975), является диофантовым аналогом класса $\mathrm{NP}$. Язык $\mathrm L$ принадлежит классу $\mathrm D$ тогда и тогда, когда существует многочлен $P$, такой, что $x$ принадлежит $\mathrm L$, если и только если существуют числа $y_i$ полиномиальной длины, такие, что $P(x,y_1,\dots,y_m)=0$.
Вопрос о равенстве классов $\mathrm D$ и $\mathrm{NP}$ открыт. В работе определяется иерархия на основе класса $\mathrm D$, аналогичная традиционной полиномиальной иерархии (на основе класса $\mathrm{NP}$) и доказывается связь между двумя иерархиями (в частности, $\mathrm{NP}$ содержится во втором уровне диофантовой иерархии). Библ. – 6 назв.