Diophantine complexity
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 3, Tome 174 (1988), pp. 122-131
Voir la notice de l'article provenant de la source Math-Net.Ru
It is well-known that every recursively enumerable set $S$ of
natural numbers can be represented as
$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$) (Davis normal form), as
$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)$)
(exponential Diophantine representation) and as
$a\in S\Leftrightarrow \exists z_1,\dots,z_n$ ($D(a,z_1,\dots,z_n)=0$)
(Diophantine representation). Each of the above three representations
enables us to introduce different complexity measures both
of the set $S$ as a whole and of accepting individual members of $S$.
The paper surveys some results by different authors connected
with such kinds of complexity measures.
@article{ZNSL_1988_174_a4,
author = {Yu. V. Matijasevich},
title = {Diophantine complexity},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {122--131},
publisher = {mathdoc},
volume = {174},
year = {1988},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_1988_174_a4/}
}
Yu. V. Matijasevich. Diophantine complexity. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 3, Tome 174 (1988), pp. 122-131. http://geodesic.mathdoc.fr/item/ZNSL_1988_174_a4/