Home

Пятница 15 апреля, 18-00, ауд. 106

Пятница, 15 апреля, ауд. 106. Начало в 18:00.

Докладчик: А.А. Кноп (СПбГУ).

Тема: Диофантова иерархия.

Abstract

Класс языков 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 содержится во втором уровне диофантовой иерархии).