Вы здесь

Сложность вычислений и основы криптографии. Лекция 6

Лекция
Партнёр:
Предмет:
Дата записи:
28.03.13
Дата публикации:
28.03.13
Код для блога:

Вероятностно проверяемые доказательства

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

Страница лекции на сайте Computer Science Center.

Другие лекции курса

11