Diophantine complexity

It is well known that any recursively enumerable set S of natural numbers can be represented by formulas of the following types a S x yx, z₁...Z_n (D (a,x,y,z₁,...,z_n)=0)¦(Davis normal form); aS z₁...z_n (E (a,z₁..., z_n)=E₂(a,z₁,...,z_n)) (exponential diophantine representation); and aS z₁... z_n, (D (a-, z₁),...)Z_n)=0) (diophantine representation). Each of these three representations yields a different measure for the complexity of S as a whole and the complexity of accepting individual members of S. A survey is presented of various results concerning such complexity measures, due to different authors.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeliniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 174, pp. 122–131, 1988.