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