143
правки
Изменения
определение графов условий
Таким образом мы показали эвивалентность <tex>\mathrm{PCP}</tex> теоремы вопросу <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex>.
}}
==Несколько определений==
{{Определение
|definition= <tex>\mathcal{C}=\lbrace c_1,..., c_n\rbrace</tex> назовем множеством условий над
множеством переменных <tex>V</tex>.
}}
{{Определение
|definition=<tex>UNSAT(\mathcal{C})</tex> — минимальное подмножество неудовлетворенных условий для любых возможных назначений <tex>V</tex>. <tex>\mathcal{C}</tex> удовлетворимо тогда и только тогда, когда <tex>UNSAT(\mathcal{C})=0</tex>. Если же <tex>\mathcal{C}</tex> неудовлетворимо, тогда <tex>UNSAT(\mathcal{C}) \ge \frac 1 n</tex>.
}}
==Графы условий==
Нам понадобятся графы ограничений для двух переменных, которые определяются следующим образом:
{{Определение
|definition=
<tex>G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle</tex> называется графом условий, если:
* <tex>(V,E)</tex> — неориентированный граф, называемый графом, леащим в основе <tex>G</tex>.
* Множество <tex>V</tex> также представляется в виде множества переменных принимающих значениями из алфавита <tex>\Sigma</tex>
* Каждое ребро <tex>e \in E</tex> содержит условие <tex>c(e) \subseteq \Sigma^2</tex> и <tex>\mathcal{C}=\lbrace c(e)\rbrace_{e \in E}</tex>. Условие <tex>c(e)</tex> называется удовлетворенным парой <tex>(a, b)</tex>, если <tex>(a, b) \in c(e)</tex>
}}
==Источники==
* [http://eccc.hpi-web.de/report/2005/046/|The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
* [http://www.cs.utah.edu/~alfeld/LecturePDFs/pcp.pdf|The PCP Theorem, Notes by Scott Alfeld, 2008]
