PCP-теорема

Материал из Викиконспекты
Версия от 15:24, 3 июня 2012; Filchenko (обсуждение | вклад) (GAP-3SAT)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Теорема ([math]\mathrm{PCP}[/math] теорема):
[math]\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}[/math]

Классическое доказательство [math]\mathrm{PCP}[/math] теоремы громоздкое и довольно сложное для восприятия, рассмотрим вариант докаательства, предложенный Динуром.

Несколько замечаний [TODO: переименовать]

Определение:
Задача [math]GAP-3SAT_s[/math]:
  • [math]\psi[/math][math]3CNF[/math] с [math]m[/math] дизъюнктами
  • [math]OPT[/math] — максимальное количество дизъюнктов, которые могуг быть удовлетворены одновременно
  • [math]OPT = m \Rightarrow YES[/math]
  • [math]OPT \lt sm \Rightarrow NO[/math]
  • [math]sm \lt OPT \lt m [/math] — нет ограничений на вывод


Лемма:
[math]\mathrm{PCP}[/math] теорема эквивалентна вопросу принадлежности [math]GAP-3SAT_s[/math] [math]\mathrm{NP}[/math] для некоторого [math]s[/math].


Источники