Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English
Что: Лекция
Когда: Среда, 22 октября 2014, 18:30–20:00
Где: ПОМИ РАН

Описание

\(NP\)-задачи поиска. Сведения по Куку. Сведение задач поиска к задачам распознавания. Оптимальный алгоритм для \(NP\)-задач поиска. Класс \(PSPACE\) и полная задача в нем. Теорема Ладнера о не \(NP\)-полном языке в классе \(NP\).