PCP-теорема

Теорема ([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].

Источники

• [PCP Theorem by Gap Amplification, Irit Dinur, 2005].