Вероятностно проверяемые доказательства. Лекция 1
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
07.10.12
Дата публикации:
07.10.12
Код для блога:
Вероятностно проверяемые доказательства и приближенные алгоритмы
Приближенные алгоритмы для MAX3SAT, вершинного покрытия. Класс PCP(r(n),q(n)), формулировка PCP-теоремы, эквивалентность PCP-теоремы и NP-трудности задачи -GAP-q-CSP, связь с трудностью приближения. Переформулировка для -GAP-3-SAT.
Страница лекции на сайте Computer Science клуба
Другие лекции курса
8