Loading AI tools
З Вікіпедії, вільної енциклопедії
У теорії обчислювальної складності, PCP теорема стверджує, що будь-яка задача розпізнавання у NP має ймовірнісно перевірювані доведення константної запитової складності і логарифмічної випадкової складності.
PCP теорема говорить, що для деякої універсальної константи K, для довільного n, всяке математичне доведення довжини n може бути переписано як інше доведення довжини poly(n), що може бути формально перевірене з 99% точністю ймовірнісним алгоритмом, що переглядає тільки K символів з цього доведення.
PCP теорема є наріжним каменем теорії обчислювальної важкості наближення, що досліджує суттєву важкість у розробці ефективних наближених алгоритмів для різних задач оптимізації.
PCP теорема формулюється у такий спосіб
Альтернативне формулювання PCP теореми стверджує, що найбільша частка виконуваних обмежень задачі виконуваності обмежень є NP-важкою для наближення з константною точністю.
Формально, для деякої константи K і α < 1, наступна задача обіцяння (Lтак, Lні) є NP-важкою задачею розпізнавання:
де Φ є задачею виконуваності обмежень у булевій абетці з не більше як 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 теореми.[1]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.