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