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