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

Описание

NP-полнота задачи Circuit-SAT и задачи о независимом множестве. NP-задачи поиска. Сведения по Тьюрингу. Сведение задач поиска к задачам распознавания. Теорема Ладнера.