143
правки
Изменения
→Графы условий: Доказательство леммы
{{Лемма
|statement=Для заданного графа условий <tex>G=\left\langle(V,E,\Sigma,\mathcal{C}\right\rangle</tex>, где <tex>|\Sigma|=3</tex> проверка утверждения <tex>UNSAT(G)=0</tex> — <tex>\mathrm{NP}</tex>-трудная задача.
|proof=TODOСведем <tex>3Color</tex> к нашей задаче. Дан граф <tex>G</tex>, алфавит <tex>\Sigma=\lbrace 1,2,3 \rbrace</tex> для трех цветов. Оснастим ребра условиями неравенства. Очевидно, что <tex>G \in 3Color</tex> тогда и только тогда, когда <tex>UNSAT(G)=0<tex> (Иногда удобно использовать одно и то же обозначение <tex>G</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]
