Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

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


Что: Лекция
Когда: Воскресенье, 07 октября 2012, 11:15–12:50
Где: ПОМИ РАН

Описание

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