RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2012 Volume 399, Pages 109–127 (Mi znsl5223)

Diophantine hierarchy

A. A. Knop

Saint-Petersburg State University, Saint-Petersburg, Russia

Abstract: 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.

Key words and phrases: Diophantine complexity.

UDC: 510.52+519.6

Received: 12.04.2012


 English version:
Journal of Mathematical Sciences (New York), 2013, 188:1, 59–69

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024