143
правки
Изменения
GAP-3SAT
{{Теорема
|id=pcp_th
|about=<tex>\mathrm{PCP}</tex> теорема
|statement=<tex>\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}</tex>
}}
Классическое доказательство [[Класс PCP|<tex>\mathrm{PCP}</tex>]] теоремы громоздкое и довольно сложное для восприятия,
рассмотрим вариант докаательства, предложенный Динуром.
==Несколько замечаний [TODO: переименовать]==
{{Определение
|definition=
Задача <tex>GAP-3SAT_s</tex>:
* <tex>\psi</tex> — <tex>3CNF</tex> с <tex>m</tex> дизъюнктами
* <tex>OPT</tex> — максимальное количество дизъюнктов, которые могуг быть удовлетворены одновременно
* <tex>OPT = m \Rightarrow YES</tex>
* <tex>OPT < sm \Rightarrow NO</tex>
* <tex>sm < OPT < m </tex> — нет ограничений на вывод
}}
{{Лемма
|statement=<tex>\mathrm{PCP}</tex> теорема эквивалентна вопросу принадлежности
<tex>GAP-3SAT_s</tex> <tex>\mathrm{NP}</tex> для некоторого <tex>s</tex>.
|proof=
}}
==Источники==
* [[http://eccc.hpi-web.de/report/2005/046/|The PCP Theorem by Gap Amplification, Irit Dinur, 2005]].
|id=pcp_th
|about=<tex>\mathrm{PCP}</tex> теорема
|statement=<tex>\mathrm{PCP}[log(n), O(1)] = \mathrm{NP}</tex>
}}
Классическое доказательство [[Класс PCP|<tex>\mathrm{PCP}</tex>]] теоремы громоздкое и довольно сложное для восприятия,
рассмотрим вариант докаательства, предложенный Динуром.
==Несколько замечаний [TODO: переименовать]==
{{Определение
|definition=
Задача <tex>GAP-3SAT_s</tex>:
* <tex>\psi</tex> — <tex>3CNF</tex> с <tex>m</tex> дизъюнктами
* <tex>OPT</tex> — максимальное количество дизъюнктов, которые могуг быть удовлетворены одновременно
* <tex>OPT = m \Rightarrow YES</tex>
* <tex>OPT < sm \Rightarrow NO</tex>
* <tex>sm < OPT < m </tex> — нет ограничений на вывод
}}
{{Лемма
|statement=<tex>\mathrm{PCP}</tex> теорема эквивалентна вопросу принадлежности
<tex>GAP-3SAT_s</tex> <tex>\mathrm{NP}</tex> для некоторого <tex>s</tex>.
|proof=
}}
==Источники==
* [[http://eccc.hpi-web.de/report/2005/046/|The PCP Theorem by Gap Amplification, Irit Dinur, 2005]].
