PCP теорема и трудность приближенного решения задач оптимизации. Часть 1

Хорошо известно, что структурная теория сложности доставляет аргументы в пользу трудности многих алгоритмических задач, в том числе и комбинаторных задач оптимизации. Свидетельством трудности является NP-полнота соответствующей задачи разрешения.
Оказывается, аналогичные доводы можно привести и в пользу трудности приближенного решения таких задач. В этом случае нужно доказывать трудность задач с априорной информацией (про вход известно, что либо все условия можно удовлетворить, либо не более некоторой доли всех условий).
Доказательства трудности таких задач основаны на анализе вероятностно проверяемых доказательств (PCP). Знаменитая PCP теорема гарантирует существование NP-полной задачи указанного выше вида и играет в теории трудности приближенных алгоритмов ту же роль, что и теорема Кука-Левина в анализе трудности задач разрешения.
В серии из двух докладов будут даны более подробные объяснения роли PCP теоремы в теории сложности, а также будет рассказано о наиболее простом ее доказательстве, предложенном Ирит Динур в 2005 году.