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

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

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