Laboratory of Mathematical Logic

Вторник, 30 января, комната 106. Начало в 12:00.

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

ВЕРОЯТНОСТНО ПРОВЕРЯЕМЫЕ ДОКАЗАТЕЛЬСТВА

Первый в серии докладов об одном из наиболее значительных достижений в структурной теории сложности 1990-х годов, положительно отвечающем на вопрос

"МОЖНО ЛИ ПРОВЕРИТЬ ДОКАЗАТЕЛЬСТВО, ПРОЧТЯ В НЕМ ЛИШЬ ТРИ БИТА?"

Язык принадлежит классу PCP(r(n),q(n)), если доказательство принадлежности к нему может быть проверено с использованием O(r(n)) случайных битов и O(q(n)) битов доказательства. Так называемая PCP Theorem гласит, что

NP = PCP(log n,1),

т.е., например, для вероятностной проверки выполнимости булевой формулы достаточно знать лишь КОНСТАНТНОЕ число

Содержание первого доклада: 1. Определения. 2. Дискуссия. 3. Связь с нижними оценками для приближенных алгоритмов.