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