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

7 октября Дмитрий Ицыксон в Computer Science клубе начнёт читать курс "Вероятностно проверяемые доказательства". Вероятностно проверяемые доказательства (Probabalistically Checkable Proofs или PCP) - это одно из самых ярких достижений теоретической информатики 90-х годов. PCP-теорема утверждает, что любое доказательство (в том числе математическое) можно переделать за полиномиальное время в такое, которое можно вероятностно проверить, прочитав лишь константное число битов этого доказательства, при этом алгоритм проверки доказательства использует лишь логарифмическое число случайных битов. Утверждение PCP-теоремы интересно и само по себе, но оно имеет важнейшее применение в теории приближенных алгоритмов для оптимизационных задач. Для многих оптимизационных задач с помощью PCP-теоремы было найдено точное значение параметра с, что существует c-приближенный полиномиальный алгоритм, но для всех c'>c существование c'-приближенного алгоритма влечет P=NP. В курсе планируется подробно разобраться со всей используемой техникой и полностью доказать PCP-теорему и ее усиленные варианты, используемые в приложениях. План курса: - Доказательство PCP-теоремы, придуманное Динур. - 3-х битная версия PCP-теоремы Хастада и следствия про трудность приближения. - Unique Game Conjecture - гипотеза, к которой сводятся очень многие вопросы о существовании приближенного алгоритма.