143
правки
Изменения
→Несколько замечаний [TODO: переименовать]: - переименовано
рассмотрим вариант докаательства, предложенный Динуром.
==Несколько замечаний [TODO: переименовать]Лемма об эквивалентности <tex>\mathrm{PCP}</tex> теоремы и <tex>\mathrm{NP}</tex>-трудности <tex>GAP-3SAT_s</tex>==
{{Определение
Таким образом мы показали эвивалентность <tex>\mathrm{PCP}</tex> теоремы вопросу <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</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]
