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 теорема є кульмінацією тривалого часу роботи над інтерактивними та ймовірнісно перевірюваними доведеннями. Першою теоремою, що пов’язує стандартні доведення та ймовірнісно перевірювані доведення є твердження, що NEXPPCP[poly(n), poly(n)], доведене Babai, Fortnow & Lund (1990).

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

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

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

Примітки[ред.ред. код]

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

Посилання[ред.ред. код]