PCP - это область, в которой вещи, абсолютно не связанные друг с другом на первый взгляд, оказываются лишь переформулировкой друг друга.

Первый сюжет таков. Многие задачи оптимизации являются NP-трудными. Однако точное значение оптимума часто не нужно, достаточно найти его приближенно. Если это можно сделать за полиномиальное время, то задачу можно считать легкорешаемой. Оказывается, для многих (но не всех!) задач даже приближенное решение с достаточной точностью будет NP-трудным.

Второй сюжет. Чтобы проверить обычное математическое доказательство, нужно прочесть его целиком. Ошибка лишь в одном переходе перечеркивает всё доказательство. Вероятностно проверяемое доказательство - такая форма записи доказательства, в которой достаточно проверить ограниченное число случайно выбранных битов, чтобы с высокой вероятностью найти ошибку. Оказывается, для любого NP-языка можно предъявить такую систему доказательств принадлежности к нему.

На первый взгляд эти два сюжета абсолютно не связаны, но на самом деле между ними можно установить эквивалентность. В мини-курсе мы подробно изучим эту эквивалентность, наметим схему доказательства знаменитой PCP-теоремы о существовании вероятностно проверяемых доказательств для всех языков из NP, а также познакомимся со сложностью приближения некоторых конкретных задач.