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

Вероятностно проверяемые доказательства (Probabalistically Checkable Proofs или PCP) - это одно из самых ярких достижений теоретической информатики 90-х годов. PCP-теорема утверждает, что любое доказательство (в том числе математическое) можно переделать за полиномиальное время в такое, которое можно вероятностно проверить, прочитав лишь константное число битов этого доказательства, при этом алгоритм проверки доказательства использует лишь логарифмическое число случайных битов. Утверждение PCP-теоремы интересно и само по себе, но оно имеет важнейшее применение в теории приближенных алгоритмов для оптимизационных задач. Для многих оптимизационных задач с помощью PCP-теоремы было найдено точное значение параметра с, что существует c-приближенный полиномиальный алгоритм, но для всех c'>c существование c'-приближенного алгоритма влечет P=NP. В курсе планируется подробно разобраться со всей используемой техникой и полностью доказать PCP-теорему и ее усиленные варианты, используемые в приложениях.

План курса:

— Доказательство PCP-теоремы, придуманное Динур.
— 3-х битная версия PCP-теоремы Хастада и следствия про трудность приближения.
— Unique Game Conjecture - гипотеза, к которой сводятся очень многие вопросы о существовании приближенного алгоритма.

Страница курса на сайте Computer Science клуба