PCP-теорема

У теорії обчислювальної складності, PCP теорема стверджує, що будь-яка задача розпізнавання у NP має ймовірнісно перевірювані доведення константної запитової складності і логарифмічної випадкової складності.

PCP теорема говорить, що для деякої універсальної константи K, для довільного n, всяке математичне доведення довжини n може бути переписано як інше доведення довжини poly(n), що може бути формально перевірене з 99% точністю ймовірнісним алгоритмом, що переглядає тільки K символів з цього доведення.

PCP теорема є наріжним каменем теорії обчислювальної важкості наближення, що досліджує суттєву важкість у розробці ефективних наближених алгоритмів для різних задач оптимізації.

PCP теорема формулюється у такий спосіб

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

PCP і важкість наближення

Альтернативне формулювання PCP теореми стверджує, що найбільша частка виконуваних обмежень задачі виконуваності обмежень є NP-важкою для наближення з константною точністю.

Формально, для деякої константи K і α < 1, наступна задача обіцяння (L_так, L_ні) є NP-важкою задачею розпізнавання:

• L_так = {Φ: всі обмеження у Φ є одночасно виконуваними}
• L_ні = {Φ: кожний розв’язок виконує менше ніж частку α обмежень Φ},

де Φ є задачею виконуваності обмежень у булевій абетці з не більше як K змінними на одне обмеження.

Як наслідок цієї теореми, може бути показано, що розв’язки до багатьох задач оптимізації включаючи задачу максимальної виконуваності, найбільшої незалежної множини у графах, і задача про найкоротший вектор для ґраток не можуть бути наближені ефективно якщо не P = NP. Ці результати інколи самі називаються PCP теоремами, оскільки їх можна розглядати як ймоврінісно перевірюване доведення для NP з деякою додатковою структурою.

Історія

PCP теорема є кульмінацією тривалого часу роботи над інтерактивними та ймовірнісно перевірюваними доведеннями. Першою теоремою, що пов’язує стандартні доведення та ймовірнісно перевірювані доведення є твердження, що NEXP ⊆ PCP[poly(n), poly(n)], доведене Babai, Fortnow та Lund, (1990).

Після цього, метод, використаний у цій роботі, було розширено Бабаєм, Фортноу, Левіним та Шеґеді у 1991 (Babai та ін., 1991), Файґе, Ґолдвасер, Лундом, Сафрою та Шеґеді (1991), і Аророю та Сафрою у 1992 (Arora та Safra, 1998), що дало змогу довести PCP теорему Аророю, Лундом, Мотвані, Суданом та Шеґеді у 1992 році (Arora та ін., 1998).

Премія Геделя за 2001 рік була присуджена Сандживу Арорі, Уріелю Файґе, Шафі Голдвасер, Карстену Лунду, Ласло Ловасу, Радживу Мотвані, Шмуелю Сафрі, Мадху Судану, та Маріо Шеґеді за роботу над PCP теоремою та її зв’язок із важкістю наближення.

У 2005 Іріт Дінур віднайшла інше доведення PCP теореми.

Посилання

• Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), Proof verification and the hardness of approximation problems, Journal of the ACM, 45 (3): 501—555, doi:10.1145/278298.278306.
• Arora, Sanjeev; Safra, Shmuel (1998), Probabilistic checking of proofs: A new characterization of NP, Journal of the ACM, 45 (1): 70—122, doi:10.1145/273865.273901.
• Babai, László; Fortnow, Lance; Levin, Leonid; Szegedy, Mario (1991), Checking computations in polylogarithmic time, STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing, ACM, с. 21—32, ISBN 978-0-89791-397-3.
• Babai, László; Fortnow, Lance; Lund, Carsten (1990), Nondeterministic exponential time has two-prover interactive protocols, SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, с. 16—25, ISBN 978-0-8186-2082-9.
• Dinur, Irit (2007), The PCP theorem by gap amplification, Journal of the ACM, 54 (3): 12, doi:10.1145/1236457.1236459.
• Feige, Uriel; Goldwasser, Shafi; Lovász, László; Safra, Shmuel; Szegedy, Mario (1996), Interactive proofs and the hardness of approximating cliques (PDF), Journal of the ACM, ACM, 43 (2): 268—292, doi:10.1145/226643.226652, ISSN 0004-5411, архів оригіналу (PDF) за 10 червня 2011, процитовано 5 травня 2011.