Diophantine complexity

Yu. V. Matijasevich

Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part 3, Tome 174 (1988), pp. 122-131

Résumé

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.