143
правки
Изменения
Графы условий без доказательсва
}}
{{Определение
|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>.
}}
}}
Присваивание это отображение <tex>\sigma:V \rightarrow \Sigma</tex>, которое назначает каждой вершине из <tex>V</tex>
значение из <tex>\Sigma</tex>. Для любого присвоения <tex>\sigma</tex> определим <tex>UNSAT_\sigma(G) = \operatorname*{Pr}\limits_{(u,v)\in E} [(\sigma(u),\sigma(v)) \notin c(e)]</tex> и <tex>UNSAT(G) = \operatorname*{min}\limits_\sigma UNSAT_\sigma(G)</tex>.
Назовем <tex>UNSAT(G)</tex> числом неудовлетворенности графа <tex>G</tex>. Размером графа будем считать размер его описания <tex>size(G)=O(|V|+|E| \cdot |\Sigma|^2)</tex>
{{Лемма
|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
}}
==Источники==
* [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]
