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

Лекция 7. Принцип Яо. PCP-теорема.
Обзорный курс по теоретической информатике


Что: Лекция
Когда: Четверг, 20 октября 2016, 18:30–19:50
Где: ПОМИ РАН

Описание

Принцип Яо (применение матричных игр для оценки сложности вероятностных алгоритмов), нижняя оценка средней сложности вероятностных алгоритмов сортировки. Две формулировки PCP-теоремы: NP-трудность GAP-3SAT и NP=PCP(log n, 1). Трудность приближения MAX3SAT и задачи о клике.