"Записки научных семинаров ПОМИ"
Том 399, стр. 109-127
Диофантова иерархия
А. А. Кноп
Санкт-Петербургский государственный
университет, Университетский пр. 28,
Петродворец, Санкт-Петербург 198504, Россия
aaknop@gmail.com
- Аннотация: Класс языков D, определённый в работе L. Adelman и K. Manders (1975),
является диофантовым аналогом класса NP.
Язык L принадлежит классу D тогда и тогда, когда существует многочлен P,
такой, что x принадлежит L если и только если существуют числа $y_i$
полиномиальной длины, такие, что $P(x,y_1,...,y_m) = 0$.
Вопрос об равенстве классов D и NP открыт.
В работе определяется иерархия на основе класса D,
аналогичная традиционной полиномиальной иерархии (на основе класса NP)
и доказывается связь между двумя иерархиями
(в частности, NP содержится во втором уровне диофантовой иерархии).
Библ. -- 6 назв.
- Ключевые слова: диофантова сложность
[Diophantine complexity]
Полный текст(.pdf)