Просмотр кода страницы Теорема PCP

В теории [[Вычислительная сложность|вычислительной сложности]] '''теорема PCP''' ({{lang-en|probabilistically checkable proofs}} — вероятностно проверяемое доказательство) утверждает, что любое решение задачи {{iw|Задача принятия решения|принятия решения|en|Decision problem}} в [[Класс сложности|классе сложности]] [[Класс NP|NP]] имеет ''вероятностно проверяемое доказательство'' (доказательство, которое можно проверить с помощью [[Вероятностный алгоритм|рандомизированного алгоритма]]) постоянной {{iw|Дерево принятия решения|сложности запроса|en|Decision tree model}} и логарифмической сложности случайности (использует логарифмическое число случайных бит).

Теорема PCP является угловым камнем теории вычислительной [[Сложность аппроксимации|сложности аппроксимации]], которая исследует врождённую сложность при разработке эффективных [[Аппроксимационный алгоритм|аппроксимационных алгоритмов]] для различных [[Оптимизация (математика)|задач оптимизации]]. Теорема отмечена {{iw|Вегенер, Инго|Инго Вегенером|en|Ingo Wegener}} как «самый важный результат в теории сложности со времён [[Теорема Кука — Левина|теоремы Кука]]»<ref name="Wegener2005">{{книга
 | автор= Ingo Wegener
 | заглавие = Complexity Theory: Exploring the Limits of Efficient Algorithms
 | издательство = Springer
 | isbn=978-3-540-21045-0
 | страница=161
 | год=2005
 | часть=Nondeterministic exponential time has two-prover interactive protocols
 | ссылка=https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA161
}}</ref> и {{iw|Голдрейх, Одед|Одедом Голдрейхом|en|Oded Goldreich}} как «кульминация цепи впечатляющих работ […], богатых новыми идеями»<ref name="Goldreich2008">{{книга
 | автор=Oded Goldreich
 | название=Computational Complexity: A Conceptual Perspective
 | ссылка=https://books.google.com/books?id=EuguvA-w5OEC&pg=PA405
 | год=2008
 | издательство=Cambridge University Press
 | isbn=978-0-521-88473-0
 | страница=405
}}</ref>.

Есть и критика. Так, в книге Босса<ref name="ReferenceA">{{книга
 | автор= Босс&nbsp;В.
 | заглавие =Перебор и эффективные алгоритмы: Учебное пособие
 | издательство =М.: Издательство ЛКИ
 | серия=Лекции по математике
 | том=10
 | isbn=978-5-382-00642-0
 | год=2008
 | страница=154
}}</ref> говорится: «В своё время это произвело фурор. Снежный ком публикаций нарастает до сих пор … Новое, по существу, определение NP-класса проливает дополнительный свет, однако без особых последствий. … Что касается самой PCP-системы, то она существенно опирается на волшебного Оракула, и поэтому не выпускает равенство '''NP''' = '''PCP'''[O(log ''n''), O(1)] в практическую плоскость».

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

: '''NP''' = '''PCP'''[O(log ''n''), O(1)]<ref name="ReferenceA"/><ref>{{статья|автор=Jose Falcon, Mitesh Jain|заглавие=An Introduction to Probabilistically Checkable Proofs and the PCP Theorem|страницы=3|год=2013|ссылка=http://www.ccs.neu.edu/home/jmitesh/pubs/intro-to-pcp.pdf|язык=|издание=|тип=|месяц=|число=|том=|номер=|issn=}}</ref>.

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

Формально, для некоторой константы ''K'' и ''α'' < 1, задача (''L''<sub>yes</sub>, ''L''<sub>no</sub>) является NP-сложной проблемой принятия решения:
* ''L''<sub>yes</sub> = {Φ: все ограничения в Φ выполнимы}
* ''L''<sub>no</sub> = {Φ: при любой подстановке доля выполненных ограничений Φ не превосходит α }.
Здесь Φ — задача о выполнении ограничивающих условий над булевским алфавитом, имеющем не более ''K'' переменных на константу<ref name="Dinur2007">
{{статья
 | автор = Irit Dinur
 | заглавие =The PCP theorem by gap amplification
 | издание =Journal of the ACM
 | том =54
 | выпуск =3
 | страницы =70—122
 | год =2007
 | doi=10.1145/1236457.1236459
}}</ref>

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

Эти результаты иногда также называют теоремами PCP, поскольку их можно рассматривать как вероятностно проверяемые доказательства NP задач с некоторыми дополнительными структурами.

== История ==
Теорема PCP — это кульминация долгого пути развития {{iw|Интерактивное доказательство|интерактивных доказательств|en|Interactive proof system}} и вероятностно проверяемых доказательств.

Первая теорема, связывающая обычные доказательства и вероятностно проверяемые доказательства, утверждала, что <math>NEXP \subseteq PCP[poly(n), poly(n)]</math>, и доказана в книге 1990-го года<ref>
{{книга
 | автор= László Babai, Lance Fortnow, Carsten Lund
 | заглавие =SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science
 | издательство =IEEE Computer Society
 | isbn=978-0-8186-2082-9
 | год=1990
 | часть=Nondeterministic exponential time has two-prover interactive protocols
 | страницы=16—25
}}</ref>.

=== История после первого доказательства теоремы в 1990 году ===
Позднее, использованный в этой статье метод, расширен в статье Бабая, Фортнова, Левина, Шегеди (1991)<ref>
{{книга
 | автор = László Babai, Lance Fortnow, Leonid Levin, Mario Szegedy
 | заглавие =STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing 
 | издательство =ACM
 | isbn=978-0-89791-397-3 
 | год=1991
 | часть=Checking computations in polylogarithmic time 
 | pages=21—32
}}</ref>, а также в статьях Фейге, Голдвассер, Лунда, Шегеди (1991), и Арора и Сафра (1992)<ref>{{ статья
 | автор = Sanjeev Arora, Shmuel Safra
 | заглавие =Probabilistic checking of proofs: A new characterization of NP
 | издание =Journal of the ACM
 | том =45
 | выпуск =1
 | страницы =70—122
 | год =1998
 | doi=10.1145/273865.273901
}}</ref>, что дало урожай в виде доказательства теоремы PCP в 1992-м году в статье Арора, Лунда, Мотвани, Судана и Шегеди<ref>{{статья
 | автор= Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy
 | заглавие=Proof verification and the hardness of approximation problems
 | издание=Journal of the ACM
 | том=45
 | выпуск=3
 | год=1998
 | страницы=501—555
 | doi=10.1145/278298.278306
}}</ref>.
В 2001-м году [[Премия Гёделя]] присуждена [[Санджив Арора|Санджив Ароре]], [[Фейге, Уриэль|Уриэлю Фейге]], [[Гольдвассер, Шафи|Шафи Голдвассер]], {{нп5|Карстен Лунд|Карстену Лунду|en|Carsten Lund}}, [[Ласло Ловас]], [[Мотвани, Раджив|Радживу Мотвани]], {{нп5|Шмуель Сафра|Шмуелю Сафра|en|Shmuel Safra}}, [[Судан, Мадху|Мадху Судану]] и {{нп5|Марио Сегеди||en|Mario Szegedy}} за работу над теоремой PCP и её связи со сложностью аппроксимации.

В 2005-м году {{iw|Ирит Динур||en|Irit Dinur}} обнаружила другое доказательство теоремы PCP, используя [[Экспандер (теория графов)|экспандеры]]<ref name="Dinur2007"/>.

=== Квантовый аналог теоремы PCP ===
В 2012-м году Томас Видик (Thomas Vidick) и Цуойши Ито (Tsuyoshi Ito) опубликовали статью<ref>{{cite web 
| url          = http://xxx.lanl.gov/abs/1207.0550 
| title        = A multi-prover interactive proof for NEXP sound against entangled provers 
| last1        = Ito 
| first1       = Tsuyoshi 
| last2        = Vidick 
| first2       = Thomas 
}}</ref>, в которой показывается «сильная ограниченность возможности сложных проверок сговора в игре многих лиц». Это важный шаг вперёд к доказательству квантового аналога теоремы PCP<ref>{{cite web 
| url          = http://www.eurekalert.org/pub_releases/2012-07/miot-mnr073012.php 
| title        = MIT News Release: 10-year-old problem in theoretical computer science falls 
| publisher    = MIT News Office 
| last         = Hardesty 
| first        = Larry 
| date         = 2012-07-30 
| accessdate   = 2012-08-10 
| archivedate  = 2012-08-10 
| archiveurl   = https://www.webcitation.org/69otwVfyT 
| quote        = Интерактивные проверки являются базисом криптографических систем и сейчас широко применяются, но для учёных в области компьютерных технологий они лишь важное средство проникновения в суть проблем сложности вычислений. 
}}</ref>, и профессор Доррит Ахаранов (Dorit Aharonov) назвала его «квантовым аналогом более ранней статьи об интерактивных проверках», которая, «по существу, вела к теореме PCP»<ref>
{{cite web 
| url          = http://web.mit.edu/newsoffice/2012/interactive-proofs-work-even-if-quantum-information-is-used-0731.html 
| title        = 10-year-old problem in theoretical computer science falls 
| publisher    = MIT News Office 
| last         = Hardesty 
| first        = Larry 
| date         = 2012-07-31 
| accessdate   = 2012-08-10 
| archivedate  = 2012-08-10 
| archiveurl   = https://www.webcitation.org/69okB9df5 
| quote        = Дори Ахаронов (Dorit Aharonov), профессор Еврейского университета в Иерусалиме, сказала, что статья Видика (Vidick) и Ито(Ito) является квантовым аналогом более ранней статьи  paper об интерактивных доказательствах, которая “по существу, вела к теореме PCP, а сама теорема PCP без сомнения является наиболее важным результатом в теории сложности за последние 20 лет”. 
Он сказал также, что новая статья “по всей видимости, является важным шагом вперед к доказательству квантового аналога теоремы PCP, которая является сейчас главным открытым вопросом в теории сложности квантовых вычислений.”
}}</ref>.

== Примечания ==
{{примечания}}

== Литература ==
* {{статья
 | автор = Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
 | заглавие = Interactive proofs and the hardness of approximating cliques
 | издание =Journal of the ACM
 | том =43
 | выпуск =2
 | год =1996
 | doi=10.1145/226643.226652
 | страницы=268—292
 | ссылка=http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf
}}

{{rq|checktranslate}}

[[Категория:Классы сложности]]