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