|
Zapiski Nauchnykh Seminarov 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.
Received: 12.04.2012
Citation:
A. A. Knop, “Diophantine hierarchy”, Computational complexity theory. Part X, Zap. Nauchn. Sem. POMI, 399, POMI, St. Petersburg, 2012, 109–127; J. Math. Sci. (N. Y.), 188:1 (2013), 59–69
Linking options:
https://www.mathnet.ru/eng/znsl5223 https://www.mathnet.ru/eng/znsl/v399/p109
|
Statistics & downloads: |
Abstract page: | 234 | Full-text PDF : | 76 | References: | 29 |
|