Сложность вычислений и основы криптографии. Лекция 6
ЛекцияПартнёр:
Предмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
28.03.13
Дата публикации:
28.03.13
Код для блога:
Вероятностно проверяемые доказательства
Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства. Формулировка PCP-теоремы. Эквивалентные формулировки. NP-трудность приближения MAX-3-SAT. Код Уолша-Адамара и его локальное декодирование.
Страница лекции на сайте Computer Science Center.
Другие лекции курса
11