1632
правки
Изменения
м
rollbackEdits.php mass rollback
Классическое доказательство [[Класс PCP|<tex>\mathrm{PCP}</tex>]] теоремы громоздкое и довольно сложное для восприятия,
рассмотрим вариант докаательства, предложенный ДинуромДинур. Оно основано на том, что <tex>\mathrm{PCP}</tex>-теорема [[Эквивалентность_PCP-теоремы_и_теоремы_о_трудности_аппроксимации | эквивалентна <tex>\mathrm{NP}</tex>-трудности задачи <tex>\rho-GAPqCSP</tex>]].
<!--
==Лемма об эквивалентности PCP теоремы и NP-трудности GAP-3SAT==
|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>
{{Лемма
|statement=Пусть <tex>G</tex> <tex>d</tex>-регулярный граф со вторым по величине собственным числом <tex>\lambda</tex>. Пусть <tex>F \subseteq E</tex> множество ребер. Вероятность <tex>p</tex> того, что случайный путь, начинающийся со случайного ребра из <tex>F</tex> на <tex>i+1</tex> шаге попадет <tex>F</tex> ограничена <tex>\frac {|F|} {|E|} + \left({\frac {|\lambda|} d}\right)^i</tex>.
|proof=см. [http://eccc.hpi-web.de/report/2005/046 The PCP Theorem by Gap Amplification, Irit Dinur, 2005]
}}
<!--
