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

Лекция 12. Вероятностно-проверяемые доказательства. Маленькие k-невависимые множества.
Обзорный курс по теоретической информатике

Что: Лекция
Когда: Понедельник, 30 ноября 2020, 18:30–19:50
Где: Конференция в zoom, Онлайн

Описание

Вероятностно-проверяемые доказательства. PCP-теорема. Эквивалентность двух формулировок. NP-трудность поиска хорошего приближенного решения для MAX-3-SAT.

Дерандомизация приближенного алгоритма для MAX-3-SAT с помощью 3-независимых множеств. Конструкция маленьких k-независимых множеств.

Видео

Другие материалы

Текущая версия конспекта.