143
правки
Изменения
убрана лемма, доказанная вдругой статье
Классическое доказательство [[Класс PCP|<tex>\mathrm{PCP}</tex>]] теоремы громоздкое и довольно сложное для восприятия,
рассмотрим вариант докаательства, предложенный Динуром. Оно основано на тос, что <tex>\mathrm{PCP}</tex>-теорема [[Эквивалентность_PCP-теоремы_и_теоремы_о_трудности_аппроксимации | эквивалентна <tex>\mathrm{NP}</tex>-трудности задачи <tex>\rho-GAPqCSP</tex>]].<!--
==Лемма об эквивалентности PCP теоремы и NP-трудности GAP-3SAT==
Таким образом мы показали эвивалентность <tex>\mathrm{PCP}</tex> теоремы вопросу <tex>\mathrm{NP}</tex>-трудности задачи <tex>GAP-3SAT_s</tex>.
}}
!-->
==Определения и леммы, используемые в доказательстве==
{{Определение
