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

Лекция 12. Вероятностно-проверяемые доказательства. Маленькие k-невависимые множества.
Introduction to Theoretical Computer Science

What: Lecture
When: Monday, 30 November 2020, 18:30–19:50
Where: Конференция в zoom, Онлайн

Description

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

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

Video

Other materials

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