Geodesic
Diophantine hierarchy
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 109-127 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Adelman and Manders (1975) defined the class $\mathrm D$ of “non-deterministic diophantine” languages. A language $\mathrm L$ is in $\mathrm D$ iff there are polynomials $p$ and $q$ such that $x\in\mathrm L\Leftrightarrow\exists\,y_1,\dots,y_ n<2^{q(|x|)}\ p(x,y_1,\dots,y_n)=0$ (in this formula, bit strings are treated as natural numbers). While clearly $\mathrm D$ is a subset of $\mathrm{NP}$, it is unknown whether these classes are equal. The well-known polynomial hierarchy PH consists of complexity classes constructed on the basis of the class $\mathrm{NP}$. We consider a hierarchy constructed on the basis of $\mathrm D$ in a similar way. We prove that $\mathrm D$ is in the second level of the polynomial hierarchy, and hence all the classes of the two hierarchies are successively contained in each other. 
@article{ZNSL_2012_399_a5,
     author = {A. A. Knop},
     title = {Diophantine hierarchy},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {109--127},
     year = {2012},
     volume = {399},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a5/}
}
TY  - JOUR
AU  - A. A. Knop
TI  - Diophantine hierarchy
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 109
EP  - 127
VL  - 399
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a5/
LA  - ru
ID  - ZNSL_2012_399_a5
ER  - 
%0 Journal Article
%A A. A. Knop
%T Diophantine hierarchy
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 109-127
%V 399
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a5/
%G ru
%F ZNSL_2012_399_a5
A. A. Knop. Diophantine hierarchy. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 109-127. http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a5/

[1] L. M. Adleman, K. L. Manders, “Computational complexity of decision procedures for polynomials”, (extended abstract), IEEE Symposium on Foundations of Computer Science, 1975, 169–177 | MR

[2] L. M. Adleman, K. L. Manders, “Diophantine complexity”, IEEE Symposium on Foundations of Computer Science, 1976, 81–88 | MR

[3] H. Lipmaa, “On Diophantine complexity and statistical zero-knowledge arguments”, ASIACRYPT' 03, 2003, 398–415 | MR | Zbl

[4] C. Pollett, “On the bounded version of Hilbert's tenth problem”, Arch. Math. Log., 42:5 (2003), 469–488 | DOI | MR | Zbl

[5] Yu. V. Matiyasevich, “Diofantovost perechislimykh mnozhestv”, Dokl. AN SSSR, 191:2 (1970), 278–282

[6] Yu. V. Matiyasevich, Desyataya problema Gilberta, Nauka, Fiziko-matematicheskaya literatura, 1993 | MR | Zbl