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

Лекция 11. Вероятностно-проверяемые доказательства
Теория сложности вычислений

Что: Лекция
Когда: Вторник, 23 ноября 2021, 18:30–19:50
Где: Конференция в zoom, Онлайн
Слайды: computationalcomplexity_lecture_231121.pdf

Описание

Приближенный алгоритм для MAX-3-SAT. Класс PCP(r(n), q(n)). GNI лежит в PCP(poly(n),1). PCP-теорема. Эквивалентная формулировка через NP-трудность задачи \(\rho\)-GAP-q-CSP. NP-трудность нахождения слишком хорошего приближения для MAX-3-SAT. Коды Уолша-Адамара и их свойства. Локальное декадирование кодов Уолша-Адамара.

Видео