Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Разрешимые и перечислимые множества. Классы P и NP
Основы вычислимости и теории сложности

Что: Лекция
Когда: Среда, 12 сентября 2012, 18:30–19:50
Где: ПОМИ РАН

Описание

Разрешимые множества, определения перечислимого множества. Теорема Поста. Классы P и NP. m-сведение, самое трудное перечислимое множество. Неразрешимость задачи об остановке алгоритма.