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

Лекция 3. Теорема Кука-Левина, задачи поиска
Computational Complexity Theory

What: Lecture
When: Tuesday, 28 September 2021, 18:30–19:50
Where: Конференция в zoom, Онлайн
Slides: computationalcomplexity_lecture_280921.pdf

Description

NP-трудность задач CircuitSAT, 3SAT, задачи о независимом множестве. NP-задачи поиска, сведение NP-задач поиска к языкам.

Video