Вы здесь

Вероятностно проверяемые доказательства. Лекция 1

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

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

Приближенные алгоритмы для MAX3SAT, вершинного покрытия. Класс PCP(r(n),q(n)), формулировка PCP-теоремы, эквивалентность PCP-теоремы и NP-трудности задачи -GAP-q-CSP, связь с трудностью приближения. Переформулировка для -GAP-3-SAT.

Страница лекции на сайте Computer Science клуба