Теорема PCP

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории вычислительной сложности, теорема PCP утверждает, что любое решение задачи принятия решения[en] в классе сложности NP имеет вероятностно проверяемое доказательство (доказательство, которое можно проверить с помощью рандомизированного алгоритма[en]) постоянной сложности запроса[en] и логарифмической сложности случайности (использует логарифмическое число случайных бит).

Теорема PCP является угловым камнем теории вычислительной сложности аппроксимации[en], которая исследует врождённую сложность при разработке эффективных аппроксимационных алгоритмов для различных задач оптимизации. Теорема была отмечена Инго Вегенером как "самый важный результат в теории сложности со времён теоремы Кука" [1] и Одедом Голдрайхом как "кульминация цепи впечатляющих работ [...], богатых новыми идеями". [2]

Есть и критика. Так, в книге Босса [3] говорится: «В своё время это произвело фурор. Снежный ком публикаций нарастает до сих пор … Новое, по существу, определение NP-класса проливает дополнительный свет , однако без особых последствий. … Что касается самой PCP-системы, то она существенно опирается на волшебного Оракула, и поэтому не выпускает равенство NP = PCP[O(log n), O(1)] в практическую плоскость».

Теорема PCP утверждает, что

NP = PCP[O(log n), O(1)][4][5].

PCP и сложность аппроксимации[править | править вики-текст]

Альтернативная формулировка теоремы PCP утверждает, что поиск максимальной доли выполненных условий в задаче о выполнении ограничивающих условий[en] является NP-трудной для аппроксимации с постоянным коэффициентом.

Формально, для некоторой константы K и α < 1, задача (Lyes, Lno) является NP-сложной проблемой принятия решения:

  • Lyes = {Φ: все ограничения в Φ выполнимы}
  • Lno = {Φ: при любой подстановке доля выполненных ограничений Φ не превосходит α }.

Здесь Φ - задача о выполнении ограничивающих условий над булевским алфавитом, имеющем не более K переменных на константу[6]

Как следствие этой теоремы можно показать, что решения многих задач оптимизации, включая поиск максимальной выполнимости булевых формул, максимального независимого множества в графе и кратчайшего вектора решётки[en], нельзя эффективно аппроксимировать, если только не выполняется P = NP. Эти результаты иногда также называют теоремами PCP, поскольку их можно рассматривать как вероятностно проверяемые доказательства NP задач с некоторыми дополнительными структурами.

История[править | править вики-текст]

Теорема PCP – это кульминация долгого пути развития интерактивных доказательств[en] и вероятностно проверяемых доказательств. Первая теорема, связывающая обычные доказательства и вероятностно проверяемые доказательства утверждала, что NEXP \subseteq PCP[poly(n), poly(n)], и доказана в книге 1990-го года (Babai, Fortnow, Lund) [7].

История после первого доказательства теоремы [в 1990][править | править вики-текст]

Позднее, использованный в этой статье метод, был расширен в статье Бабая, Фортнова, Левина, Шегеди (1991) [8], а также в статьях Фейге, Голдвассер, Лунда, Шегеди (1991), и Арора и Сафра (1992) [9], что дало урожай в виде доказательства теоремы PCP в 1992-м году в статье Арора, Лунда, Мотвани, Судана и Шегеди [10] В 2001-ом году Премия Гёделя была присуждена Санджив Ароре (Sanjeev Arora), Уриэлю Фейге (Uriel Feige), Шафи Голдвассер (Shafi Goldwasser), Карстену Ланду (Carsten Lund), Ласло Ловашу (László Lovász), Раджииву Мотвани (Rajeev Motwani), Шмуэлю Шафра (Shmuel Safra), Мадху Судану (Madhu Sudan), и Марио Шегеди (Mario Szegedy) за работу над теоремой PCP и её связи со сложностью аппроксимации.

В 2005-ом году Ирит Динур (Irit Dinur) обнаружила другое доказательство теоремы PCP, используя экспандеры.[6]

Квантовый аналог теоремы PCP[править | править вики-текст]

В 2012-ом году Томас Видик (Thomas Vidick) и Цуойши Ито (Tsuyoshi Ito) опубликовали статью[11], в которой показывается "сильная ограниченность возможности сложных проверок сговора в игре многих лиц". Это важный шаг вперед к доказательству квантового аналога теоремы PCP,[12] и профессор Доррит Ахаранов (Dorit Aharonov) назвала его "квантовым аналогом более ранней статьи об интерактивных проверках", которая, " по существу, вела к теореме PCP,".[13]

Примечания[править | править вики-текст]

  1. Ingo Wegener Nondeterministic exponential time has two-prover interactive protocols // Complexity Theory: Exploring the Limits of Efficient Algorithms. — Springer, 2005. — ISBN 978-3-540-21045-0
  2. Oded Goldreich Computational Complexity: A Conceptual Perspective. — Cambridge University Press, 2008. — ISBN 978-0-521-88473-0
  3. Босс В. Лекции по математике. Т.10: Перебор и эффективные алгоритмы: Учебное пособие. — М.: Издательство ЛКИ, 2008. — ISBN 978-5-382-00642-0
  4. Jose Falcon, Mitesh Jain An Introduction to Probabilistically Checkable Proofs and the PCP Theorem. — 2011. — С. 3..
  5. Босс В. Лекции по математике. Т.10: Перебор и эффективные алгоритмы: Учебное пособие. — М.: Издательство ЛКИ, 2008. — ISBN 978-5-382-00642-0
  6. 1 2 Irit Dinur The PCP theorem by gap amplification // Journal of the ACM. — 2007. — В. 3. — Т. 54. — С. 12. — DOI:10.1145/1236457.1236459.
  7. László Babai, Lance Fortnow, Carsten Lund Nondeterministic exponential time has two-prover interactive protocols // SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science. — IEEE Computer Society, 1990. — С. 16–25. — ISBN 978-0-8186-2082-9
  8. László Babai, Lance Fortnow, Leonid Levin, Mario Szegedy Checking computations in polylogarithmic time // STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing. — ACM, 1991. — P. 21–32. — ISBN 978-0-89791-397-3
  9. Sanjeev Arora, Shmuel Safra Probabilistic checking of proofs: A new characterization of NP // Journal of the ACM. — 1998. — В. 1. — Т. 45. — С. 70–122. — DOI:10.1145/273865.273901.
  10. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy Proof verification and the hardness of approximation problems // Journal of the ACM. — 1998. — В. 3. — Т. 45. — С. 501–555. — DOI:10.1145/278298.278306.
  11. A multi-prover interactive proof for NEXP sound against entangled provers.
  12. Hardesty, Larry MIT News Release: 10-year-old problem in theoretical computer science falls. MIT News Office (30 июля 2012). — «Интерактивные проверки являются базисом криптографических систем и сейчас широко применяются, но для учёных в области компьютерных технологий они лишь важное средство проникновения в суть проблем сложности вычислений.»  Проверено 10 августа 2012. Архивировано из первоисточника 10 августа 2012.
  13. Hardesty, Larry 10-year-old problem in theoretical computer science falls. MIT News Office (31 июля 2012). — «Дори Ахаронов (Dorit Aharonov), профессор Еврейского университета в Иерусалиме, сказала, что статья Видика (Vidick) и Ито(Ito) является квантовым аналогом более ранней статьи paper об интерактивных доказательствах, которая “, по существу, вела к теореме PCP, а сама теорема PCP без сомнения является наиболее важным результатом в теории сложности за последние 20 лет.” Он сказал также, что новая статья, “по всей видимости, является важным шагом вперед к доказательству квантового аналога теоремы PCP, которая является сейчас главным открытым вопросом в теории сложности квантовых вычислений.”»  Проверено 10 августа 2012. Архивировано из первоисточника 10 августа 2012.
  • Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy Interactive proofs and the hardness of approximating cliques // Journal of the ACM. — 1996. — В. 2. — Т. 43. — С. 268–292. — DOI:10.1145/226643.226652.