Пятница, 15 апреля, ауд. 106. Начало в 18:00.
Докладчик: А.А. Кноп (СПбГУ).
Тема: Диофантова иерархия.
Abstract
Класс языков D, определённый в работе L. Adelman и K. Manders (1975),
является диофантовым аналогом класса NP.
Язык L принадлежит классу D тогда и тогда, когда существует многочлен
![$ P $](../../../sites/default/files/tex/eefbe23045963a19db197b822a2436586412b6e6/index.png)
,
такой, что
![$ x $](../../../sites/default/files/tex/33fe5a238412ce3cd054309829bfa5d804965124/index.png)
принадлежит L если и только если существуют числа
![$ y_i $](../../../sites/default/files/tex/0f213d5785e9725f0cf2002d527d119bba7cac38/index.png)
полиномиальной длины, такие, что
![$ P(x,y_1,...,y_m) = 0. $](../../../sites/default/files/tex/2d9bb424883af05b8240b481c6300cdb52bb1524/index.png)
Вопрос о равенстве классов D и NP открыт.
В докладе определяется иерархия на основе класса D,
аналогичная традиционной полиномиальной иерархии (на основе класса NP)
и доказывается связь между двумя иерархиями
(в частности, NP содержится во втором уровне диофантовой иерархии).