City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Разрешимые и перечислимые множества. Классы P и NP
Foundations of computability and complexity theory

What: Lecture
When: Wednesday, 12 September 2012, 18:30–19:50
Where: ПОМИ РАН

Description

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

Video