PCP-теорема

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

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

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

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

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

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

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

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

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

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

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

Історія

PCP теорема є кульмінацією тривалого часу роботи над та ймовірнісно перевірюваними доведеннями. Першою теоремою, що пов’язує стандартні доведення та ймовірнісно перевірювані доведення є твердження, що ⊆ 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 теореми.

Примітки

1. Див. препринт 2005 року, . Прорецензованю версією є стаття Dinur, (2007).

Посилання

• ; ; ; ; (1998), Proof verification and the hardness of approximation problems, Journal of the ACM, 45 (3): 501—555, doi:10.1145/278298.278306.
• ; (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ó; ; Levin, Leonid; (1991), Checking computations in polylogarithmic time, STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing, ACM, с. 21—32, ISBN .
• Babai, László; ; 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 .
• Dinur, Irit (2007), The PCP theorem by gap amplification, Journal of the ACM, 54 (3): 12, doi:10.1145/1236457.1236459.
• ; ; Lovász, László; ; (1996), (PDF), , ACM, 43 (2): 268—292, doi:10.1145/226643.226652, ISSN 0004-5411, архів оригіналу (PDF) за 10 червня 2011, процитовано 5 травня 2011.