Laboratory of Mathematical Logic at PDMI

Вторник, 6 февраля, комната 106. Начало в 11:59.

Докладчик: Э. Гирш.

ДОКАЗАТЕЛЬСТВО PCP THEOREM
Будет приведено доказательство первой (более простой) части PCP Theorem, иначе говоря, доказано, что для проверки выполнимости булевой формулы достаточно проверить всего лишь КОНСТАНТНОЕ количество битов "доказательства" (при этом разрешается использовать O(n^3) случайных битов).
Необходимые определения будут повторены (впрочем, они фактически содержатся в предыдущем абзаце).
Web-page семинара: http://logic.pdmi.ras.ru/~hirsch/minisem/ Подписка: email по адресу majordomo@logic.pdmi.ras.ru с командой SUBSCRIBE _minisem