|
Записки научных семинаров ПОМИ, 2012, том 399, страницы 109–127
(Mi znsl5223)
|
|
|
|
Диофантова иерархия
А. А. Кноп Санкт-Петербургский государственный университет, Санкт-Петербург, Россия
Аннотация:
Класс языков $\mathrm D$, определённый в работе L. Adelman и K. Manders (1975), является диофантовым аналогом класса $\mathrm{NP}$. Язык $\mathrm L$ принадлежит классу $\mathrm D$ тогда и тогда, когда существует многочлен $P$, такой, что $x$ принадлежит $\mathrm L$, если и только если существуют числа $y_i$ полиномиальной длины, такие, что $P(x,y_1,\dots,y_m)=0$.
Вопрос о равенстве классов $\mathrm D$ и $\mathrm{NP}$ открыт. В работе определяется иерархия на основе класса $\mathrm D$, аналогичная традиционной полиномиальной иерархии (на основе класса $\mathrm{NP}$) и доказывается связь между двумя иерархиями (в частности, $\mathrm{NP}$ содержится во втором уровне диофантовой иерархии). Библ. – 6 назв.
Ключевые слова:
диофантова сложность.
Поступило: 12.04.2012
Образец цитирования:
А. А. Кноп, “Диофантова иерархия”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 109–127; J. Math. Sci. (N. Y.), 188:1 (2013), 59–69
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl5223 https://www.mathnet.ru/rus/znsl/v399/p109
|
Статистика просмотров: |
Страница аннотации: | 219 | PDF полного текста: | 69 | Список литературы: | 19 |
|