Главная
В теории вычислительной сложности теорема PCP (англ. probabilistically checkable proofs — вероятностно проверяемое доказательство) утверждает, что любое решение задачи принятия решения в классе сложности NP имеет вероятностно проверяемое доказательство (доказательство, которое можно проверить с помощью рандомизированного алгоритма) постоянной сложности запроса и логарифмической сложности случайности (использует логарифмическое число случайных бит).
Теорема PCP является угловым камнем теории вычислительной сложности аппроксимации, которая исследует врождённую сложность при разработке эффективных аппроксимационных алгоритмов для различных задач оптимизации. Теорема отмечена Инго Вегенером как «самый важный результат в теории сложности со времён теоремы Кука» и Одедом Голдрейхом как «кульминация цепи впечатляющих работ […], богатых новыми идеями».
Есть и критика. Так, в книге Босса говорится: «В своё время это произвело фурор. Снежный ком публикаций нарастает до сих пор … Новое, по существу, определение NP-класса проливает дополнительный свет, однако без особых последствий. … Что касается самой PCP-системы, то она существенно опирается на волшебного Оракула, и поэтому не выпускает равенство NP = PCP[O(log n), O(1)] в практическую плоскость».
Теорема PCP утверждает, что
NP = PCP[O(log n), O(1)].PCP и сложность аппроксимации
Альтернативная формулировка теоремы PCP утверждает, что поиск максимальной доли выполненных условий в задаче о выполнении ограничивающих условий является NP-трудной для аппроксимации с постоянным коэффициентом.
Формально, для некоторой константы K и α < 1, задача (Lyes, Lno) является NP-сложной проблемой принятия решения:
- Lyes = {Φ: все ограничения в Φ выполнимы}
- Lno = {Φ: при любой подстановке доля выполненных ограничений Φ не превосходит α }.
Здесь Φ — задача о выполнении ограничивающих условий над булевским алфавитом, имеющем не более K переменных на константу
Как следствие этой теоремы можно показать, что решения многих задач оптимизации, включая поиск максимальной выполнимости булевых формул, максимального независимого множества в графе и кратчайшего вектора решётки, нельзя эффективно аппроксимировать, если только не выполняется P = NP.
Эти результаты иногда также называют теоремами PCP, поскольку их можно рассматривать как вероятностно проверяемые доказательства NP задач с некоторыми дополнительными структурами.
История
Теорема PCP — это кульминация долгого пути развития интерактивных доказательств и вероятностно проверяемых доказательств.
Первая теорема, связывающая обычные доказательства и вероятностно проверяемые доказательства, утверждала, что N E X P ⊆ P C P [ p o l y ( n ) , p o l y ( n ) ] {displaystyle NEXPsubseteq PCP[poly(n),poly(n)]} , и доказана в книге 1990-го года.
История после первого доказательства теоремы в 1990 году
Позднее, использованный в этой статье метод, расширен в статье Бабая, Фортнова, Левина, Шегеди (1991), а также в статьях Фейге, Голдвассер, Лунда, Шегеди (1991), и Арора и Сафра (1992), что дало урожай в виде доказательства теоремы PCP в 1992-м году в статье Арора, Лунда, Мотвани, Судана и Шегеди. В 2001-м году Премия Гёделя присуждена Санджив Ароре, Уриэлю Фейге, Шафи Голдвассер, Карстену Лунду, Ласло Ловас, Радживу Мотвани, Шмуелю Сафра, Мадху Судану и Марио Сегеди за работу над теоремой PCP и её связи со сложностью аппроксимации.
В 2005-м году Ирит Динур обнаружила другое доказательство теоремы PCP, используя экспандеры.
Квантовый аналог теоремы PCP
В 2012-м году Томас Видик (Thomas Vidick) и Цуёси Ито (Tsuyoshi Ito) опубликовали статью, в которой показывается «сильная ограниченность возможности сложных проверок сговора в игре многих лиц». Это важный шаг вперёд к доказательству квантового аналога теоремы PCP, и профессор Дорит Ахаронов (Dorit Aharonov) назвала его «квантовым аналогом более ранней статьи об интерактивных проверках», которая, «по существу, вела к теореме PCP».