City: Saint Petersburg Novosibirsk Kazan Language: Русский English
What: Lecture
When: Wednesday, 31 October 2012, 18:30–19:50
Where: ПОМИ РАН

Description

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